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

Question

题目要求:PrimeGeneratorhttp://www.spoj.com/problems/PRIME1/要求计算最多10组，每组由两个数m,n构成(1

Answer 1

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