C++欧拉函数-题目一 求欧拉函数

解题思路

1. 分解质因数；
2. 代入公式计算即可（注意要防止计算出小数是结果不准）；

代码实现

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

void Euler(int n)
{
    int sq = sqrt(n);
    
    int t = n;    
    
    for(int i = 2;i <= sq;i ++ )//分解质因数；
    {
        if(n % i == 0)
        {
            t = t - t / i;// 不能用t = t * (1 - 1 / i)，因为会计算出小数使结果不准；
            while(n % i == 0)
            {
                n /= i;
            }
        }
    }
    
    if(n > 1)
    {
        t = t - t / n;
    }
    
    cout << t << endl;
}

int main()
{
    int n, a;
    
    cin >> n;
    
    while(n -- )
    {
        scanf("%d", &a);
        Euler(a);
    }
    return 0;
}