在ACM会经常遇到使用大量素数的情景，谷歌了一下，当不是特别多时，可以使用筛选法搞定. 这个wiki上扒来的原理图: 埃拉托斯特尼筛法，简称埃氏筛，是一种公元前250年由古希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。 下面是伪代码:
// arbitrary search limitlimit ← 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 ∈ {n2, n2+n, n2+2n, ..., limit}for n in [2, limit]: if is_prime(n): print n
针对上面的思路，Python代码如下
prime_dic = {}prime_list = []n = 1000for i in range(2, n + 1):prime_dic[i] = 1for 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] = 0for k, v in prime_dic.items():if v == 1:prime_list.append(k)print prime_list
原文地址：快速素数产生, 感谢原作者分享。 有事者，事竟成;破釜沉舟，百二秦关终归楚;苦心人，
