递推欧拉函数

  1. /*=======================================================* 
  2.  |               递推求欧拉函数phi(i)
  3.  欧拉函数varphi(n)是小于或等于n的正整数中与n互质的数的数目
  4. *=======================================================*/ 
  6. #define N 3000000
  7. __int64 phi[N + 100];
  9. void Euler()
  10. {
  11. 	int i, j;
  12. 	for(i = 1; i < N; i++)
  13. 	    phi[i] = i;
  14. 	
  15. 	for(i = 2; i < N; i++)
  16. 	    if(i == phi[i])								//若i为素数 第一次不是
  17. 	        for(j = i; j < N; j += i)				//让j累加i
  18. 	            phi[j] = (phi[j] / i) * (i - 1);	//求欧拉函数
  19. }





附件列表

    【推广】 免费学中医，健康全家人
    原文地址：https://www.cnblogs.com/sober-reflection/p/73ee2f34434d0439ac2d7038cec12b4d.html