筛法求欧拉函数

筛法求欧拉函数

给定一个正整数 n，求 1∼n中每个数的欧拉函数之和。
输入格式
共一行，包含一个整数 n。
输出格式
共一行，包含一个整数，表示 1∼n中每个数的欧拉函数之和。
数据范围
1≤n≤106
输入样例：
6
输出样例：
12

#include<iostream>
#include<algorithm>using namespace std;typedef long long ll;const int N = 1000010;int primes[N],cnt;
int phi[N];
bool st[N];ll get_eulers(int n){phi[1] = 1;for(int i=2;i<=n;i++){//线性筛法if(!st[i]){//i为质数primes[cnt++] = i;phi[i] = i-1;//和i互质的数的个数            }for(int j=0;primes[j]<=n/i;j++){st[primes[j]*i] = true;if(i%primes[j]==0){ phi[primes[j]*i] = primes[j] * phi[i];//推导出phi的一般情况,i是以primes为质数的倍数    break;}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_eulers(n)<<endl;return 0;
}