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

The screening method cannot meet the requirements of the question in terms of time complexity, and timeout is inevitable. Use the sieve method to find all prime numbers (about 3400) less than sqrt(1000000000), and then use these prime numbers to sift again to determine whether the number between [m, n] is a prime number.

Or try fermat test or miller-rabin test Because it is a probabilistic algorithm, you can WA.

Answer 2

Finally passed, because the previous sieve was not a prime number, so it was slower. First, filter out the prime numbers between 2-sqrt(1,000,000,000), and then sift it, it will be very fast. The modified code looks like this. The code structure may not be very good, but the logic is correct.

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