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

Question

题目要求:PrimeGeneratorhttp://www.spoj.com/problems/PRIME1/
要求计算最多10组，每组由两个数m,n构成(1<=m<=n<=1000000000,n-m<100000),要求打印出m,n之间的所有素数（包括m,n），时间限制6s。下面是我采用筛法写的python代码，但是仍然超时，到底是哪里错了呢？
我写的代码：
frommathimportsqrt
defPrimeGenerator():
n=input()
a=range(n)
foriinrange(n):
a[i]=raw_input().split()
foraaina:
start=int(aa[0])
end=int(aa[-1])
length=end-start+1
l=[True]*length
foriinrange(2,int(sqrt(end))+1):#筛子
ifstart==1:#排除1
k=i*2
whilek<=end:
l[k-start]=False
k+=i
l[0]=False
elifstart==2:#2是素数
k=i*2
whilek<=end:
l[k-start]=False
k+=i
else:#有一些下限值小于筛子的情况
k=start<=iandi*2ori*(start/i)
whilek<=end:
ifk>=start:
l[k-start]=False
k+=i
foriinrange(length):
ifl[i]:
printi+start
print
PrimeGenerator()

Answer 1

筛法从时间复杂度上就没法满足题目的要求，超时是必然的。筛法求出小于sqrt(1000000000)的所有素数（大约3400个），然后用这些素数再筛一次来判断[m,n]之间的数是否是素数。或者试试fermattest或者miller-rabintest吧因为是概率算法，会WA。