给定一个正整数 nn,求 1∼n1∼n 中每个数的欧拉函数之和。
输入格式
共一行,包含一个整数 nn。
输出格式
共一行,包含一个整数,表示 1∼n1∼n 中每个数的欧拉函数之和。
数据范围
1≤n≤1061≤n≤106
输入样例:
6
输出样例:
12
//2021/11/14 #include <iostream> #include <cstring> #include <algorithm> using namespace std; #define int long long #define endl "\n" void sky(int n); const int N = 1000010; int primes[N], cnt; int euler[N]; bool st[N]; signed main() { int n; cin>>n; int cnt=0; sky(n); for (int i = 1; i <= n; i ++ ) cnt+=euler[i]; cout<<cnt; } void sky(int n) { euler[1] = 1; for (int i = 2; i <= n; i ++ ) { if (!st[i]) { primes[cnt ++ ] = i; euler[i] = i - 1; } //质数的欧拉函数为i-1 for (int j = 0; primes[j] <= n / i; j ++ ) { int t = primes[j] * i; st[t] = true; if (i % primes[j] == 0) { euler[t] = euler[i] * primes[j]; break; } euler[t] = euler[i] * (primes[j] - 1); } //补充 如果gcd(m, n) = d 则 f(m∗n)=f(m)∗f(n)∗d/f(d) } }