总而言之就是

  • 2筛出4;# ×2
  • 2,3筛出6,9;# ×3
  • 2,3筛出8;# ×4,4%2==0,直接跳出,故不计3×4=12,又因为2是4的最小素因子,所以4*3=(2*2)*3=2*(2*3)=2*6=12,即12会被6筛出,此处不需要多此一举
  • 2,3,5筛出10,15,25;# ×5
  • 2,3,5筛出12,18,30;# ×6,同理,6%2==3,后面的3,5不需要算了,因为6*5=(2*3)*5=2*(3*5)=2*15=30被15筛出,此处若计算3,5将多出大量无用计算
  • 是否跳过多余计算比较:

Code:

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
# -*-coding:utf-8-*-
maxl = 1000000  # 筛选范围
count = 0       
ss = []    # 素数
check = [] # 0代表素数，1代表合数。全部初始化为素数。
for x in range(0, maxl+1):
	check.append(0)
# 筛选出 2~10^6 所有素数
for i in range(2, maxl):
	# 如果是素数就存起来
	if check[i] == 0:
		ss.append(i)
		count += 1
	# 循环存起来的素数
	for j in range(0, count):
		# 素数的i倍，肯定是一个合数
		if ss[j]*i > maxl:
			break
		# 将素数的i倍标注为合数，这儿将所有素数视为最小素数，那么最小素数对应的所有合数都会被标注。
		check[ss[j]*i] = 1
		# 循环素数列表，如果被筛选的数能被列表中某个数整除，由于列表中的素数是有序的，所以该素数就是被筛选数的最小素因子。
		# 我们知道上一句代码就是用来筛选出素因子对应合数的，既然合数 i 对应的最小素因子已经在素数列表中了，那么合数 i 肯定
		# 会被改素数给筛选出，所以结束当前循环，没必要用其他素数去筛选 i 
		if i%ss[j] == 0:
			break
print(ss[:100])