SGU 102（欧拉函数）
欧拉函数： phi（x）=x(1-1/p1)(1-1/p2)****(1-1/pn); pi为x的质因数
#include
bool prim[10001];
int n;
int main()
{
for(int i = 2;i <=100;i++)
for(int j = 2;i*j<=10000;j++)
prim[i*j] = 1;
while(scanf("%d",&n)==1)
{
int ans=n;
for(int i = 2; i <= n; i++)
if(!prim[i]&&n%i==0)
{
ans = ans/i*(i-1);
}
printf("%d\n",ans);
}
return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！