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;
}

题目二 线性筛法求欧拉函数

解题思路

重要数学公式：

1. 欧拉函数 ϕ(N) ,如果N为质数，则ϕ(N) = N - 1（代入一般公式可得）；
2. ϕ(NM)， 如果N,M互为质数，则ϕ(NM) = ϕ(N) * ϕ(M);

解题步骤：

1. 代入线性筛法求质数的模板；
2. 根据条件，结合上述数学公式记录每个数的欧拉函数；
3. 累加即可；

代码实现

#include<iostream>

using namespace std;

const int N = 1e6 + 10;

bool st[N];//判断是否被筛掉
int primes[N];//存质数
int prime_nums[N];//存储每个数的欧拉函数
int cnt;//存质数个数

void get_primes(int n)
{
    prime_nums[1] = 1;//1的欧拉函数为1（定义）
    
    for(int i = 2;i <= n;i ++ )
    {
        if(!st[i])
        {
            primes[cnt ++ ] = i;
            prime_nums[i] = i - 1;//质数的欧拉函数为其本身减一
        }
        
        for(int j = 0;primes[j] <= n / i;j ++ )
        {
            st[primes[j] * i] = true;
            
            if(i % primes[j] == 0)//primes[j]是i的最小质因数(下以pj代指primes[j])
            {
                prime_nums[primes[j] * i] = primes[j] * prime_nums[i];
                //pj是i最小质因数，若i分解质因数得p1^e1*^p2^e2^...pk^ek^;
                //则pj*i分解质因数等于p1^e1^*p2^e2^...pk^ek^（e1 ... ek某处+1),底数不变，指数某处+1;
                //代入欧拉公式等于pj*i*(1-1/p1)*(1-1/p2)...(1-1/pk) == pj*prime_nums[i];
                //也就是说pj等于p1,p2...pk中的一个数!!!
                break;
            }
            //pj和i互质:
            prime_nums[primes[j] * i] = prime_nums[i] * (primes[j] - 1);
            //pj不是i最小质因数，若i分解质因数得p1^e1^*p2^e2^...pk^ek^;
            //则pj*i分解质因数等于pj*p1^e1^*p2^e2^...pk^ek^;
            //代入欧拉公式等于pj*i*(1-1/pj)*(1-1/p1)*(1-1/p2)...(1-1/pk) == (pj-1)*prime_nums[i];
            //也就是说pj不等于p1,p2...pk中的任何一个数!!!
        }
    }
    
    long long res = 0;
    
    for(int i = 1;i <= n;i ++ )
    {
        res += prime_nums[i];
    }
    
    cout << res;
}

int main()
{
    int n;
    
    cin >> n;
    
    get_primes(n);
    
    return 0;
}