注意以下三个特殊性质
编程实现 利用欧拉函数和它本身不同质因数的关系,用筛法计算出某个范围内所有数的欧拉函数值。
1 //直接求解欧拉函数
2 #include<cstdio>
3 int euler(int n){ //返回euler(n)
4 int res=n,a=n;
5 for(int i=2;i*i<=a;i++){//从小到大尝试n的质因数
6 if(a%i==0){//如果i是n的质因数
7 res=res/i*(i-1);//提了一个1/i出来,先进行除法是为了防止中间数据的溢出
8 while(a%i==0) a/=i;//欧拉函数只记算一种质因数
9 }
10 }
11 if(a>1) res=res/a*(a-1);//如果最后还剩因子
12 return res;
13 }
14 int main(){
15 int x;
16 scanf("%d",&x);
17 printf("%d",euler(x));
18 return 0;
19 }
1 //筛选法打欧拉函数表
2 #include<cstdio>
3 #define Max 1000001
4 int euler[Max];
5 void Init(){
6 euler[1]=1;
7 for(int i=2;i<Max;i++)
8 euler[i]=i;
9 for(int i=2;i<Max;i++)
10 if(euler[i]==i)//如果i是质数
11 for(int j=i;j<Max;j+=i)
12 euler[j]=euler[j]/i*(i-1);//提一个1/i,先进行除法是为了防止中间数据的溢出
13 return ;
14 }
15 int main()
16 {
17 Init();
18 for(int i=1;i<=100;i++)
19 printf("%d\n",euler[i]);
20 return 0;
21 }