文章目錄

在欧拉工程中,很多时候都需要用到素数,而得到素数比较好就是用筛法生成。筛法还是很容易理解的,随便找一本教科书的可以找到。

有了这个函数后,要得到100以内的素数就非常容易了。

1
2
3
4
5
6
7
8
9
10
11
12
13
def getPrimes(n):
primes = [True for i in xrange(n + 1)]
primes[0] = primes[1] = False
for x in xrange(2, n + 1):
if not primes[x]:
continue
m = x * x
while m <= n:
primes[m] = False
m += x
return [i for i in xrange(n + 1) if primes[i]]

print get_primes(100)

2014年8月16日更新:
才发现这个函数的速度还不理想,于是改成

1
2
3
4
5
6
7
8
9
def getPrimes(n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
i = 2
while i * i <= n:
if primes[i]:
primes[i * i:n + 1:i] = [False] * ((n - i * i) / i + 1)
i += 1
return [i for i in xrange(n + 1) if primes[i]]

之所以这么改,可参看Python筛法求素数的优化

文章目錄