题目描述

给定 n 个正整数 ai，请你求出每个数的欧拉函数。

欧拉函数的定义
1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
若在算数基本定理中，N=pa11pa22…pamm，则：
ϕ(N) = N×p1−1p1×p2−1p2×…×pm−1pm
输入格式
第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式
输出共 n 行，每行输出一个正整数 ai 的欧拉函数。

数据范围
1≤n≤100,
1≤ai≤2×109

样例

输入样例：
3
3
6
8
输出样例：
2
2
4

看代码

C++ 代码

#include <iostream>
#include <cmath>
using namespace std;
//欧拉函数的通式ϕ(N) = N*(1-1/p1)*(1-1/p2)*(1-1/p3)*...*(1-1/pm)
//pm是N的质因数
int  (int n)
{
    int i,ret=n;
    for(i=2; i<=sqrt(n); i++)
    {
        if(n%i==0)
        {
            ret=ret/i*(i-1);// /i*(i-1)=*(1-1/i)
            while(n%i==0) n/=i;//把i除干净,质因数有一个就行
        }
    }
    if(n>1) ret=ret/n*(n-1);//n>1说明n也是一个质因数
    return ret;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        cout<<eular(x)<<endl;
    } 

    return 0;
}