本文共 676 字，大约阅读时间需要 2 分钟。
输入一个数N。(2 <= N <= 10^9)
输出Phi(n)。
8
4
数论中的问题，太深奥，只能学习学习了
#include/*1. 将n表示成素数的乘积: n = p1 ^ k1 * p2 ^ k2 * ... * pn ^ kn（这里p1, p2, ..., pn是素数）2. PHI(n) = (p1 ^ k1 - p1 ^ (k1 - 1)) * (p2 ^ k2 - p2 ^ (k2 - 1)) * ... *(pn ^ kn - pn ^ (kn - 1)) = Mult { pi ^ ki - pi ^ (ki -1) }*/int main(){ int N; scanf("%d",&N); int res=N; for(int i=2;i*i<=N;++i){ if(N%i==0){ res-=res/i; while(N%i==0)N/=i;//保证i一定是素数 } } printf("%d\n",N>1?res/N*(N-1):res); return 0;}
转载地址：http://scvvi.baihongyu.com/