Hdu2824 快速求欧拉函数和

#include<iostream>
using namespace std;

const int maxn = 3000000 + 10;
__int64 p[maxn];

void init(){
for(int i=1; i<maxn; i++){
p[i] = i;
}
for(int i=2; i<maxn; i++){
if(p[i] == i){
for(int j=i; j<maxn; j += i){ //注意j是i的倍数(约数)
p[j] = p[j] * (i - 1) /i;
}
}
}
}

int main(){
init();
int a, b;
while(cin>>a>>b){
__int64 ans = 0;
for(int i=a; i<=b; i++){
ans += p[i];
}
cout<<ans<<endl;
}
return 0;
}

原文：http://www.cnblogs.com/cbyniypeu/p/3526166.html