By

文章目錄

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

有了这个函数后，要得到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筛法求素数的优化

打赏作者

文章目錄