题目描述
题目要求:给定n个数求出,n个数的欧拉数;
1——n中互质的数的数量
欧拉函数:
基本思路:在求每一个数的质因子的过程中利用欧拉函数进行计算
C++ 代码
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
int a;
cin>>a;
int res=a;
for(int i=2;i<=a/i;i++)
{
if(a%i==0)
{
res=res/i*(i-1);
while(a%i==0)
{
a/=i;
}
}
}
if(a>1) res=res/a*(a-1);
printf("%d\n",res);
}
return 0;
}