线性筛素数顺便求解欧拉函数

(线性欧拉筛) $O(n)$

时间复杂度

参考文献

线性筛素数的文章链接可参看博客：埃氏筛法和线性筛法求素数
此文完整版见博客利用线性筛法求素数的方法顺便求解1~n的欧拉函数的全过程

C++ 代码

//在线性欧拉筛素数的基础上计算欧拉函数，巧妙，效率高。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1000000+7;
int primes[N],phi[N];
bool st[N];
LL getEulers(int n){
    phi[1] = 1;
    int cnt = 0;
    for(int i = 2;i<= n; i++){
        if(!st[i]){
            primes[++cnt] = i;
            phi[i] = i-1;      //性质1
        }
        for(int j = 1;j<= cnt && primes[j]*i <=n; j++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0){
                phi[primes[j] * i] = primes[j] * phi[i];   //性质2
                break;
            }
            else{
                phi[primes[j] * i] = (primes[j] - 1) * phi[i];   //性质3
            }
        }
    }
    LL ans = 0;
    for(int i = 1; i<= n; i++){
        ans = ans + phi[i];
    }
    return ans;
}
int main(){
    int n;
    scanf("%d",&n);
    LL ans = getEulers(n);
    printf("%lld",ans);
    return 0;
}