Python编程：筛法求两个数之间的素数

Question

题目要求:Prime Generator http://www.spoj.com/problems/PRIME1/ 要求计算最多10组，每组由两个数m,n构成(1&lt;=m&lt;=n&lt;=1000000000,n-m&lt;100000),要求打印出m,n之间的所有素数（包括m,n），时间限制6s。...

伊谢尔伦 · Answer

~~筛法从时间复杂度上就没法满足题目的要求，超时是必然的。~~ 筛法求出小于sqrt(1000000000)的所有素数（大约3400个），然后用这些素数再筛一次来判断[m, n]之间的数是否是素数。

~~或者试试 fermat test 或者 miller-rabin test 吧~~因为是概率算法，会WA。

伊谢尔伦 · Answer

终于过了，由于之前的筛子不是素数，所以比较慢。先把2-sqrt(1,000,000,000)之间的素数过滤出来，再去筛就很快了。修改之后的代码是这样的，代码结构可能不是很好，但是逻辑是对的。

from math import sqrt

def Primes(primes=[]):
    for i in range(3,31622,2):
        isprime = True
        cap = sqrt(i)+1
        for j in primes:
            if (j >= cap):
                break
            if (i % j == 0):
                isprime = False
                break
        if (isprime):
            primes.append(i)

def PrimeGenerator():
    primes = [2]
    Primes(primes)

    n = input()
    a = range(n)

    for i in range(n):
        a[i] = raw_input().split()

    for aa in a:
        start = int(aa[0])
        end = int(aa[-1])
        length = end - start + 1
        l = [True] * length
        for i in primes:
            if i > sqrt(end):
                break
            if start == 1:
                k = i * 2
                while k <= end:
                    l[k-start] = False
                    k += i
                l[0] = False
            elif start == 2:
                k = i * 2
                while k <= end:
                    l[k-start] = False
                    k += i
            else:
                k = start <= i and i * 2 or i * (start / i)
                while k <= end:
                    if k >= start:
                        l[k-start] = False
                    k += i
        for i in range(length):
            if l[i]:
                print i + start
        print

PrimeGenerator()

ringa_lee · Answer

http://www.zhihu.com/question/24236455/answer/27138389