筛法求欧拉函数

思路：

（1）若要分别求1~n每个数的欧拉函数值，则复杂度O（n*n^0.5)，超时；

（2）于是考虑用欧拉筛进行求取；

（3）欧拉筛：基于线性筛，在筛质数与合数过程中，递推求取欧拉值：

1. 对于质数x，欧拉值为x - 1，因为除其自身外，1~n - 1均与其互质；
2. 对于合数i,如果i%primes[j] == 0,则i*primes[j]与i质因子相同，于是有ph[i*primes[j] ] = ph[i]*primes[j];如果i%primes[j] != 0；则i*primes[j]与i质因子差一个质数primes[j]，于是有ph[i*primes[j] ] = ph[i]*(primes[j] - 1)/primes[j] *primes[j];

代码：

#include<bits/stdc++.h>using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
LL primes[N],ph[N],st[N],cnt;void euler(int n)
{ph[1] = 1;for(int i = 2;i <= n;i ++){if(st[i] == 0){primes[cnt ++] = i;ph[i] = i  - 1;}for(int j = 0; primes[j]*i <= n;j ++){st[primes[j] * i ] = 1;if(i % primes[j] == 0){ph[primes[j] * i] = ph[i] * primes[j];break;}ph[primes[j] * i] = ph[i] * (primes[j] - 1);}}LL res = 0;for(int i = 1;i <= n;i ++){res += ph[i];}cout << res;
}int main()
{int n;cin >> n;euler(n);return 0;
}