快速素数产生
Fish (fsh267@gmail.com)发表于 2014-02-07 00:00:00
在ACM会经常遇到使用大量素数的情景，谷歌了一下，当不是特别多时，可以使用筛选法搞定.
这个wiki上扒来的原理图:
埃拉托斯特尼筛法，简称埃氏筛，是一种公元前250年由古希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。
下面是伪代码:
// arbitrary search limit
limit ← 1.000.000
// assume all numbers are prime at first
is_prime(i) ← true, i ∈ [2, limit]
for n in [2, √limit]:
if is_prime(n):
// eliminate multiples of each prime,
// starting with its square
is_prime(i) ← false, i ∈ {n², n²+n, n²+2n, ..., limit}
for n in [2, limit]:
if is_prime(n): print n针对上面的思路，Python代码如下
prime_dic = {}
prime_list = []
n = 1000
for i in range(2, n + 1):
prime_dic[i] = 1
for i in range(2, int(n ** .5) + 1):
for j in range(i ** 2, n + 1, i):
if prime_dic[i] == 1:
prime_dic[j] = 0
for k, v in prime_dic.items():
if v == 1:
prime_list.append(k)
print prime_list