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

输入格式

共一行，包含一个整数 n。

输出格式

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

数据范围

1≤n≤

输入样例：

6

输出样例：

12

代码：

#include<iostream>
using namespace std;const int N = 1000010;
int n,cnt;
int phi[N],att[N],Primes[N];long long Get_eulers(int n){long long res = 0;phi[1] = 1;for(int i = 2; i <= n;i ++){if(att[i] == 0){Primes[cnt] = i;cnt++;phi[i] = i - 1;}for(int j = 0;Primes[j] <= n / i;j++){att[i * Primes[j]] = 1;if(i % Primes[j] == 0){phi[i * Primes[j]] = phi[i] * Primes[j];break;}else{phi[i * Primes[j]] = phi[i] * (Primes[j] - 1);}}}for(int i = 0;i <= n;i ++){res += phi[i];}return res;
}int main(){cin>>n;long long ans = Get_eulers(n);cout<<ans<<endl;return 0;
}