欧拉函数（优化）2@亿万星辰
//基于欧拉公式对欧拉函数代码进行优化
#include <stdio.h>
int main()
{
int ans,n;
scanf("%d",&n);
ans=n;
for(int i=2;i*i<=n;i++)//查找
{
if(n%i==0)
{
ans*=(i-1.0)/i;//定义公式
while(n%i==0) n/=i*1.0;//找出n的因数中与i互质的最大因数
}
}
if(n>1) ans*=(n-1)*1.0/n;//补充for循环中漏掉的质因数
printf("%d",ans);
return 0;
}
欧拉函数优化，今日份学习
腾讯开奖367人在聊
