题目描述

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

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

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

数据范围
1≤n≤106

样例

输入样例：
6
输出样例：
12

看代码

C++ 代码

#include <iostream>
using namespace std;

typedef long long ll;

const int p=1000010;
//根据线性筛写的
int primes[p],cnt;//primes储存质数，cnt表示质数的多少，和线性筛一样

int phi[p];//phi表示1-n中每个数的欧拉函数的大小

bool st[p];

ll get_eular(int n)
{
    phi[1]=1;//规定1的欧拉函数为1
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            primes[cnt++]=i;//把质数存入primes数组，然后求这个质数的欧拉函数
            phi[i]=i-1;//我们可以发现一个质数它的欧拉函数的值为i-1
            //比如5,5的质因数只有5本身，所以5的欧拉函数=5*（1-1/5）=4
        }
    for(int j=0;primes[j]<=n/i;j++)
      {
        st[primes[j]*i]=true;
        if(i%primes[j]==0)//如果i%primes[j]=0,说明i是i*primes[j]的一个质因数，所以i的所有质因数
        //就可以用来表示i*primes[j]的所有质因数
        {
            //所以由欧拉函数公式可得phi[primes[j]*i]=phi[i]*primes[j]
            phi[primes[j]*i]=phi[i]*primes[j];
            break;
        }
        //如果i%primes[j]!=0,则求i的全部质因数后，因为primes[j]也是一个质因数
        //所以也要加上primes[j]
        //即phi[primes[j]*i]=phi[i]*primes[j]*(1-1/primes[j])=phi[i]*(primes[j]-1)
        phi[primes[j]*i]=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_eular(n)<<endl;
    return 0;
 }