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

• euler函数： $\varphi \left(n\right)=n\ast {\prod }_{i=1}^k(1-\frac{1}{p_i})$ϕ(n)=n∗∏i=1k​(1−pi​1​)
  首先， $\varphi \left(n\right)$ϕ(n)表示小于或等于n的数中，与n互质的数的个数。特别的， $\varphi \left(n\right)$ϕ(n)=1。对于这个公式的理解：n以内的正整数有n个，而根据唯一因数分解定理又可得知n可以拆分成 ${\prod }_{i=1}^k{p}_i^{a_i}$∏i=1k​piai​​，所以只需要把各个质因数所占的概率密度扣除最后乘以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); 
      }
    }
  }
}