euler函数以及筛法求1~n的euler值

euler函数： $ϕ (n) = n * \prod_{i = 1}^{k} (1 - \frac{1}{p_{i}})$
首先， $ϕ (n)$ 表示小于或等于n的数中，与n互质的数的个数。特别的， $ϕ (n)$ =1。对于这个公式的理解：n以内的正整数有n个，而根据唯一因数分解定理又可得知n可以拆分成 $\prod_{i = 1}^{k} p_{i}^{a_{i}}$ ，所以只需要把各个质因数所占的概率密度扣除最后乘以n就是剩下的与n互质的数的个数。

代码实现：

求n的欧拉值

//求euler函数Ø(x) 求小于等于x中与x互质的数的个数 Ø(1) = 1
int eulerfun(int x) {
  int res = x;
  for (int i = 2; i <= sqrt(x); i++) {
    if (x % i == 0) {
      res = res / i * (i - 1);
      while(x % i == 0) x /= i;
    }
  }
  if (x > 1) {
    res = res / x * (x - 1);
  }
  return res;
}

筛法求1~n的欧拉值

//埃氏筛求1~n的euler值
const maxn = (int)1e6+5;
int phi[maxn];
void eulerP1(int n) {
  for (int i = 1; i < maxn; i++) phi[i] = i;
  for (int i = 2; i < maxn; i++) {
    if (phi[i] == i) { //说明是质数，比它小的数字不会筛到它
      for (int j = i; j < maxn; j += i) {
        //这样写的原因是到达j的时候默认比它小的质因数的概率密度都算好了，只需把他这个i的质因数的密度算好即可
        phi[j] = phi[j] / i * (i - 1); 
      }
    }
  }
}