洛谷p2568 gcd

#define LL long long
const int N=10000050;
bool used[N];
int n,phi[N],prime[N>>3],cnt=0;
LL ans=0,sum[N];
void ()
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if (!used[i]) prime[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt;j++)
        {
            if (prime[j]*i>n) break;
            used[i*prime[j]]=1;
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
            if (i%prime[j]==0) {phi[i*prime[j]]+=phi[i];break;}
        }
    }
}
int main()
{
    scanf("%d",&n);
    work();
    for(int i=1;i<=n;i++) 
        sum[i]=sum[i-1]+phi[i];
    for(int i=1;i<=cnt;i++)
        ans=ans+sum[n/prime[i]]*2-1;
    printf("%lld",ans);	
    return 0;
}