线性筛法求欧拉函数之和$O(n)$
核心:在找到质数和筛掉合数时,利用欧拉函数的公式直接计得出其欧拉函数
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1000010;
int primes[N], cnt;
int euler[N];
bool st[N];
void get_eulers(int n)
{
euler[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
euler[i] = i - 1;
//如果一个数a是质数,那么它的欧拉函数是a-1
}
for (int j = 0; primes[j] <= n / i; j ++ )
{
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0)
//当pj是i的质因子时,pj的质因子都在i的质因子中,因此pj*i的质因子与i的质因子相
//同,而一个数的欧拉函数与其质子的次数无关,因此推导公式得:φ(pj*i)=pj*φ(i)
{
euler[t] = euler[i] * primes[j];
break;
}
//当pj不是i的质因子时,pj*i的质因子只比i的质因子多一个pj,因此φ(pj*i)的展开式在
//φ(i)的展开式中多乘上一项(1-1/pj)和pj即可,推导化简得:φ(pj*i)=(pj-1)φ(i)
euler[t] = euler[i] * (primes[j] - 1);
}
}
}
int main()
{
int n;
cin >> n;
get_eulers(n);
LL res = 0; //最后的答案要开long long 数据是1e6
for (int i = 1; i <= n; i ++ ) res += euler[i];
cout << res << endl;
return 0;
}