用Python实现欧拉筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
N = 1000010

def get_prime():
global cnt

for i in range(2,n+1):
if not st[i]:
cnt += 1
# 不管是合数还是质数,都用来筛掉它的倍数
for j in range(i,n+1,i):
st[j] = True

def get_prime_egypt():
global cnt

for i in range(2,n+1):
if not st[i]:
cnt += 1
# 可以用质数就把所有合数筛掉
for j in range(i,n+1,i):
st[j] = True

# 保证n只会被它的最小质因子筛掉(埃式筛法比如6会被2和3都筛一次)
def get_prime_linear():
global cnt

for i in range(2,n+1):
if not st[i]:
primes[cnt] = i
cnt += 1

# 内层循环判断primes[j]>n/i就break,保证primes[j]*i < n,st数组不会越界
for j in range(cnt):
if prime[j]>n/i: break
st[prime[j]*i] = True
if i%prime[j] == 0: break

if __name__ == '__main__':
primes, cnt, st = [0]*N, 0, [False]*N
n = int(input())
get_prime_linear()
print(cnt)

由于普通筛选和埃式筛都比较简单,就不过多讲解了,这里主要看线性筛。

核心思想:在埃氏筛法的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。

(1) 首先来看,合数一定会被筛掉

1
2
假设pj(prime[j])是x的最小质因子,当i循环到x/pj的时候,就会被筛掉。
所以 i 在消去合数中的作用是当做倍数的,i 又是从2到n,肯定可以消完所有合数。

(2) 再来看为什么可以保证每个合数是用其最小质数筛掉的

·枚举到i的最小质因子的时候就会停下来,即if(i%primes[j]==0)break;
·当i%primes[j]!=0时,primes[j]一定小于i的最小质因子,primes[j]一定是primes[j]*i的最小质因子;
·当i%primes[j]==0时,primes[j]一定小于i的最小质因子,而primes[j]一定是primes[j]的最小质因子,因此primes[j]一定是primes[j]*i的最小质因子;

1
2
3
4
这里引出了一个问题,为什么要在 == 0 的时候break
当 i 是 prime[j] 的倍数时,有i = k * prime[j] ,如果继续运算 j+1
i * prime[j+1] = prime[j] * k * prime[j+1] # 这里prime[j]是最小的质因子
当 i 循环到 = k * prime[j+1] 时会和 i * prime[j+1] 重复 # 所以要跳出循环。

(3) 再来看在循环的时候不必要加上判断j < cnt:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
// j < cnt 不必要,因为 primes[cnt - 1] = 当前最大质数
// 如果 i 不是质数,肯定会在中间就 break 掉
// 如果 i 是质数,那么 primes[cnt - 1] = i,也保证了 j < cnt
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}

 (4) 最后来看内层 for 循环的结束条件

1
内层循环判断primes[j]>n/i就break,保证primes[j]*i < n,st数组不会越界

转载自这里