素数筛法|欧拉函数|欧拉筛法 埃氏筛法 详解

定义

欧拉函数是由$n$指向小于等于$n$且与$n$互质的正整数个数的函数，用$phi(n)$表示。

example

$$phi(2) = 1，（1）$$

$$phi(3) = 2，（1，2）$$

$$phi(4) = 2，（1，3）$$

$$phi(5) = 4，（1，2，3，4）$$

$$phi(6) = 2，（1，5）$$

公式

结论

假设n的质因数分解为$p_1^a \times p_2^b \times ... \times p_m^k$（$p_i$是质因数），则欧拉函数可以用公式求得：

$$phi(n) = n \times (1- \cfrac{1}{p_1} ) \times (1- \cfrac{1}{p_2} ) \times ... \times (1-\cfrac{1}{p_m})$$

推导

首先一个数$x$与$n$互质，说明没有公共的质因子，即$x$不能有$p_1$、$p_2$、…$p_m$等质因子。
那么$1...n$中有$p_1$质因子的个数为$\cfrac{n}{p_i}$。
同样，对质因子$p_i$，$1...n$中有$\cfrac{n}{p_i}$个 数带$p_i$质因子。
显然，没有$p_i$的质因子的数量，就是要减去$\cfrac{n}{p_i}$，即$n-sum(\cfrac{n}{p_i})$。

加上重复减去的数，根据容斥原理就得到了：

$$phi(n) = n - sum( \cfrac{n}{p_i} ) + sum( \cfrac{n}{p_i \times p_j} ) - ... + (-1)^m \times \cfrac{n}{p_1 \times p_2} \times ...\times p_m =n(1- \cfrac{1}{p_1}) \times (1-\cfrac{1}{p_2})...(1-\cfrac{1}{p_m})$$

朴素算法

1

根据定义，直接枚举$1...n$里与$n$的最大公约数是1的个数。

1
2

for(int i=1; i<=n; i++)
  ans += gcd(n, i)==1;

2

根据公式

$$phi(n) = n \times (1- \cfrac{1}{p_1} ) \times (1- \cfrac{1}{p_2} ) \times ... \times (1-\cfrac{1}{p_m})$$

循环求质因子，在过程中计算 ans=ans*(1-1/pi) ,即 ans-= ans/pi

1
2
3
4
5
6
7
8

ans = n;
for(int i=2; i*i<=n; i++) {
  if(n%i==0) {
    ans -= ans/i;
    while(n%i==0) n/=i;
  }
}
if(n>1) ans -= ans/n;

筛法解法

埃氏筛法

根据欧拉函数的定义，

$$phi(x)=x \times (1- \cfrac{1}{p_i})$$

埃氏筛法的原理是用素数$p_i$ 筛所有的倍数$j \times p_i$，说明此时$j \times p_i$有一个质因数$p_i$，因此可以用上面的公式进行递推。

• 首先 phi[x] = x
• 对每个素数$p_i$的倍数 j , 有phi[j] *= (1-1/pi)，也即phi[j] -= phi[j]/pi
  • 如果对于某个i，其phi[i] != i，说明之前筛过，是合数

1
2
3
4
5
6
7
8
9

void shai(int mx) {
  for(int i=1; i<=mx; i++)
    phi[i] = i;
  for(int i=2; i<=mx; i++) {
    if(phi[i] != i) continue;
    for(int j=i; j<=mx; j+=i)
      phi[j] -= phi[j]/i;
  }
}

欧拉筛法

对于某个质数$p_i$，分两种情况分析：

1. 如果是x的质因子，则对$x \times p_i$ 来说，pi已经在欧拉函数里计算了$(1-\cfrac{1}{p_i})$，因此有：$phi(x \times p_i) = phi(x) \times p_i$
2. 如果不是x的质因子，则对$x \times pi$来说又多了一个质因子，有：$phi(x \times p_i) = phi(x) \times p_i \times (1- \cfrac{1}{p_i}) = phi(x) \times (p_i - 1)$

结合欧拉筛法，就可以求phi[x]的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void shai(int mx) {
  phi[1] = 1;
  for(int i=2; i<=mx; i++) {
    if(!notPrime[i]) {
      p[++last] = i;
      phi[i] = i-1;
    }
    for(int j=1; j<=last; j++) {
      int t = i * p[j];
      if(t>=mx) break;
      notPrime[t] = true;
      if(i % p[j]==0) {
        phi[t] = phi[i] * p[j];
        break;
      } else
       phi[t]= phi[i] * (p[j]-1);
    }
  }
}