题目要求: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()
筛法从时间复杂度上就没法满足题目的要求，超时是必然的。筛法求出小于sqrt(1000000000)的所有素数（大约3400个），然后用这些素数再筛一次来判断[m, n]之间的数是否是素数。或者试试 fermat test 或者 miller-rabin test 吧因为是概率算法，会WA。终于过了，由于之前的筛子不是素数，所以比较慢。先把2-sqrt(1,000,000,000)之间的素数过滤出来，再去筛就很快了。修改之后的代码是这样的，代码结构可能不是很好，但是逻辑是对的。
http://www.zhihu.com/question/24236455/answer/27138389