题目描述

给定一个正整数n，求1~n中每个数的欧拉函数之和。

输入格式
共一行，包含一个整数n。

输出格式
共一行，包含一个整数，表示1~n中每个数的欧拉函数之和。

数据范围
1≤n≤106

样例

输入样例：
6

输出样例：
12

算法

(线性筛法) $O(n)$

当i%p[j]的值为0，(p[j] * i)的欧拉函数值 = p[j] * i的欧拉函数值
否则，(p[j] * i)的欧拉函数值 = i的欧拉函数值 * p[j] * (1-1/p[j])

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
typedef long long LL;
int n,primes[N],phi[N],cnt;
bool st[N];
LL euler(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            phi[i]=i-1;     //1到p-1都和p互质
        }
        for(int j=0;primes[j]<=n/i;j++){
            int t=primes[j]*i;
            st[t]=true;
            if(i%primes[j]==0){     //p[j]*i的所有质因子都出现在i的所有质因子当中
                phi[t]=phi[i]*primes[j];
                break;
            }
            phi[t]=phi[i]*(primes[j]-1);    //比i的所有质因子多了一个p[j]
        }
    }
    LL res=0;
    for(int i=1;i<=n;i++) res+=phi[i];
    return res;
}
int main(){
    scanf("%d",&n);
    printf("%lld\n",euler(n));
    return 0;
}