C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1000010;
typedef long long LL;
int primes[N] , euler[N] , n;
bool st[N];
LL get_euler(int u)
{
euler[1] = 1;
int cnt = 0;
for(int i = 2; i <= n; i++) // 求从1 到 n 的欧拉数
{
if(st[i] == 0)
{
primes[cnt++] = i;
euler[i] = i - 1;
}
for(int j = 0; primes[j] <= u / i; j++)
{
st[primes[j] * i] = 1;
if(i % primes[j] == 0)
{
euler[i * primes[j]] = euler[i] * primes[j]; // 因为prime【j】为i以及i * prime是【j】的最小质因子,所以eule[i]已经包括primes【j】
// 所以根据公式euler[i * primes[j]]只需要 euler[i] * primes[j]即可;
break;
}
euler[i * primes[j]] = euler[i] * (primes[j] - 1); // 因为primes[j] 与 i 互为质数 所以 euler[i * primes[j]] 需要把primes[j]这个质因子减去
//所以根据公式 euler[i * primes[j]]的值需要 euler[i] *euler[i] * (primes[j] - 1);
}
}
LL res = 0;
for(int i = 1; i <= n; i++)
{
res = res + euler[i];
}
return res;
}
int main()
{
cin >> n;
cout << get_euler(n) << endl;
return 0;
}