The Euler function

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5923    Accepted Submission(s): 2501 Problem Description The Euler function phi is an important kind of function in number theory, (n) represents the amount of the numbers which are smaller than n and coprime to n, and this function has a lot of beautiful characteristics. Here comes a very easy question: suppose you are given a, b, try to calculate (a)+ (a+1)+....+ (b)   Input There are several test cases. Each line has two integers a, b (2<a<b<3000000).   Output Output the result of (a)+ (a+1)+....+ (b)   Sample Input 3 100   Sample Output 3042 #include<cstdio> #include<cstring> typedef long long LL; LL num[3100000]; void Init() { memset(num,0,sizeof(num)); LL n,j; num[1]=1; for(n=2;n<3000010;++n) { if(!num[n]) { for(j=n;j<3000010;j+=n) { if(!num[j]) num[j]=j; num[j]=num[j]*(n-1)/n; } } } } int main() { Init(); LL a,b; while(~scanf("%lld%lld",&a,&b)) { LL sum=0; for(;a<=b;++a) sum+=num[a]; printf("%lld\n",sum); } return 0; }