#include<iostream> #include<cstdio> #include<cstdlib> const int N=100; int phi[N],prime[N]; int main() { int i,j; prime[0]=prime[1]=0; for(i=2;i<N;i++) { prime[i]=1; } for(i=2;i*i<N;i++) { if(prime[i]) { for(j=i*i;j<=N;j+=i) { prime[j]=0; } } } //這段求出了N內的所有素數 for(i=1;i<N;i++) { phi[i]=i; } for(i=2;i<N;i++) { if(prime[i]) { for(j=i;j<N;j+=i) { phi[j]=phi[j]/i*(i-1); //此處注意先/i再*（i-1)，否則範圍較大時會溢位 } } } for(i=0;i<N;i++) printf("%d\n",phi[i]); } /* 尤拉公式：phi(x) = (p1-1)/p1*(p2-1)/p2....*(pn-1)/pn * x 推導過程如下： x=p1^k1*p2^k2*……pn^kn,對於某個數m=a^b(a為質數)，與m不互質的數只有a的倍數,即m/a,即a^(b-1),所以與m互質的個數為m-m/a=a^b-a^(b-1); 類似地，phi(x)=[p1^k1-p1^(k1-1)]*[p2^k2-p2^(k2-1)]……*[pn^kn-pn^(kn-1)] =[p1^(k1-1)*(p1-1)]*[p2^(k2-1)*(p2-1)]……*[pn^(kn-1)*(pn-1)] =[p1^(k1-1)*p2^(k2-1)……*pn^(kn-1)]*[(p1-1)*(p2-1)*……*(pn-1)] =x*[(p1-1)*(p2-1)....*(pn-1)]/[(p1-1)*(p2-1)*……*(pn-1)] */