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

Question

题目要求:Prime Generator http://www.spoj.com/problems/PRIME1/

要求计算最多10组，每组由两个数m,n构成(1<=m<=n<=1000000000,n-m<100000),要求打印出m,n之间的所有素数（包括m,n），时间限制6s。下面是我采用筛法写的python代码，但是仍然超时，到底是哪里错了呢？

我写的代码：

from math import sqrt

def PrimeGenerator():
    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 range(2, int(sqrt(end)) + 1):  # 筛子
            if start == 1:   # 排除1
                k = i * 2
                while k <= end:
                    l[k-start] = False
                    k += i
                l[0] = False
            elif start == 2: # 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()

Answer 1

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

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

Answer 2

终于过了，由于之前的筛子不是素数，所以比较慢。先把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()

Answer 3

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