HDU 2824 The Euler function

篩法計算歐拉函數

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=3000005;
long long phi[maxn];
int main(){int i,j,a,b;for(i=1;i<=maxn;i++) phi[i]=i;for(i=2;i<=maxn;i+=2) phi[i]/=2;for(i=3;i<=maxn;i+=2)if(phi[i]==i){for(j=i;j<=maxn;j+=i)phi[j]=phi[j]/i*(i-1);}while(scanf("%d%d",&a,&b)!=EOF){long long ans=0;for(i=a;i<=b;i++)ans+=phi[i];cout<<ans<<endl;}return 0;
}