快速素数产生

// 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

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