解题思路:
注意事项:
参考代码:
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int N=2000010; int prime[N],cnt=0; int res[11],num[11],n,m,tmp;//m记录质数的个数 bool p[N]; void FindPrime(int n) { for(int i=2;i<=n;i++) { if(p[i]==false) { prime[++cnt]=i; for(int j=i+i;j<=n;j+=i) p[j]=true; } } } int main(void) { cin>>n; tmp=n; FindPrime(n); //cout<<"cnt="<<cnt<<endl; //for(int i=1;i<=cnt;i++) cout<<prime[i]<<" "; cnt=1; while(n!=1) { if(n%prime[cnt]==0) { res[++m]=prime[cnt]; while(n%prime[cnt]==0) { num[m]++; n/=prime[cnt]; } } cnt++; } for(int i=1;i<=m;i++) { tmp/=res[i]; tmp*=res[i]-1; } cout<<tmp<<endl; return 0; }
0.0分
1 人评分