注意以下三个特殊性质

编程实现

  利用欧拉函数和它本身不同质因数的关系，用筛法计算出某个范围内所有数的欧拉函数值。

1 //直接求解欧拉函数   2 #include
       
         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
       
         3 #define Max 1000001   4 int euler[Max];   5 void Init(){ 6     euler[1]=1; 7     for(int i=2;i