本文共 1434 字，大约阅读时间需要 4 分钟。

如何高效计算1到n的欧拉函数之和

欧拉函数φ(n)表示小于等于n且与n互质的正整数的个数。为了计算1到n中每个数的欧拉函数之和，我们可以使用线性筛法，这种方法的时间复杂度为O(n log log n)，非常高效。

方法概述

代码实现

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
typedef long long LL;
const int N = 1e6 + 7;
int primes[N], cnt;
bool st[N];
LL get_eulers(int n) {
    st[1] = true;
    for (int i = 2; i <= n; ++i) {
        if (!st[i]) {
            primes[cnt++] = i;
            st[i] = true;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; ++j) {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0) {
                phi[t] = phi[i] * primes[j];
                break;
            }
            phi[t] = phi[i] * (primes[j] - 1);
        }
    }
    LL res = 0;
    for (int i = 1; i <= n; ++i) {
        res += phi[i];
    }
    return res;
}
int main() {
    int n;
    cin >> n;
    cout << get_eulers(n) << endl;
    return 0;
}
     
    
   

代码解释

• 初始化：st数组用于标记已处理的数，primes数组存储质数，phi数组存储每个数的欧拉函数值。
• 遍历质数：对于每个数i，若未被标记，则为质数，加入primes数组，并计算其欧拉函数值。
• 处理倍数：对于每个质数p，处理其倍数t，根据t的质因数分解情况计算欧拉函数值。
• 累加结果：遍历所有数，累加欧拉函数值，返回结果。

这种方法高效且适用于大范围的n，能够快速计算1到n的欧拉函数之和。

转载地址：http://gaefk.baihongyu.com/