c++ 欧拉函数前缀和

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N=1e7+5;
int primes[N], phi[N], cnt=0;
bool vis[N];
LL s[N];


void Lsieve(int n){
    memset(primes, 0x00, sizeof primes);
    memset(phi, 0x00, sizeof phi);
    memset(vis, 0x00, sizeof vis);
    memset(s, 0x00, sizeof s);
    phi[1]=1;

    for(int i=2; i<=n; ++i){
        if(!vis[i]) {primes[cnt++]=i; phi[i]=i-1;}
        for(int j=0; primes[j]<=n/i; ++j){
            vis[primes[j]*i]=true;
            if(i%primes[j]==0){phi[i*primes[j]]=phi[i]*primes[j]; break;}
            else phi[i*primes[j]]=phi[i]*(primes[j]-1);
        }
        s[i]=s[i-1]+phi[i];
    }
}

int main(){
    int n;
    cin>>n;
    Lsieve(n);
    LL ans=0;
    for(int i=0; i<cnt; ++i){
        int p=primes[i];
        ans+=s[n/p]*2+1;
    }
    cout<<ans<<endl;

    return 0;
}