The Euler function
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2986 Accepted Submission(s): 1221
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
第一种打表的方法是，素数和欧拉，分开来打表。250ms
第二种打表只有一个，但是时间上更多。500ms
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 8 int prime[3000003],len; 9 int opl[3000003];10 bool s[3000003];11 12 void Getprime() //打素数表13 {14 int i,j;15 len=0;16 for(i=2;i<=3000000;i++)17 {18 if(s[i]==false)19 {20 prime[++len]=i;21 for(j=i*2;j<=3000000;j=j+i)22 s[j]=true;23 }24 }25 }26 27 void Euler() //欧拉打表。28 {29 int i,j;30 Getprime();31 for(i=2;i<=3000000;i++)32 opl[i]=i;33 opl[1]=0;34 for(i=1;i<=len;i++)35 {36 for(j=prime[i];j<=3000000;j=j+prime[i])37 opl[j]=opl[j]/prime[i]*(prime[i]-1); //利用的定理38 39 }40 }41 42 int main()43 {44 int n,m,i;45 __int64 num;46 Euler();47 while(scanf("%d%d",&n,&m)>0)48 {49 num=0;50 for(i=n;i<=m;i++)51 num=num+opl[i];52 printf("%I64d\n",num);53 }54 return 0;55 }
第二种方法。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 8 int opl[3000003]; 9 bool s[3000003];10 11 12 void Euler() //欧拉打表。13 {14 int i,j;15 for(i=2;i<=3000000;i++)16 opl[i]=i;17 opl[1]=0;18 19 for(i=2;i<=3000000;i++)20 if(s[i]==false)21 {22 for(j=i;j<=3000000;j=j+i)23 {24 opl[j]=opl[j]/i*(i-1);25 s[j]=true;26 }27 }28 }29 30 int main()31 {32 int n,m,i;33 __int64 num;34 Euler();35 while(scanf("%d%d",&n,&m)>0)36 {37 num=0;38 for(i=n;i<=m;i++)39 num=num+opl[i];40 printf("%I64d\n",num);41 }42 return 0;43 }