运行s的Python质数代码

Question

我试图解决这里提到的问题：https://www.spoj.pl/problems/PRIME1/

我也给出了下面的描述。在

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

Input

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.`

我的代码如下。我认为删除列表上的方法很慢。在

import sys
import math

num = int(sys.stdin.readline());
indices = []
maxrange = 2
while(num > 0):
    a,b = sys.stdin.readline().split(" ");
    a = int(a)
    b = int(b)
    if(a < 2):
        a = 2
    indices.append((a,b))
    if(b > maxrange):
        maxrange= b          
    num = num - 1

val = int(math.sqrt(maxrange)+1)
val2 = int(math.sqrt(val)+1)
checks = range(2,val2)

for i in range(2,val2):
    for j in checks:
        if(i!= j and j%i == 0):
            checks.remove(j)

primes = range(2,val)
for i in checks:
    for j in primes:
        if(i != j and j%i == 0):
            primes.remove(j)

primes2 = range(2,maxrange)
for i in primes:
    for j in primes2:
        if(j != i and j%i == 0):
            primes2.remove(j)

for (a,b) in indices:
    for p in primes2:
        if(a<= p and b >= p):
            print p
        if(p > b):
            break
    print

我认为python列表删除非常慢。我的代码是正确的，但我已经超过了时间限制。有人能帮我改进这个代码吗。在

Answer 1

与其删除不是质数的元素，不如用一些sentinel值替换它，比如-1或{}？然后在打印时，只需打印不是哨兵的值。在

使用一个长度为(n-m)的列表，那么编号i的索引是x[m+i]。在

Answer 2

素性测试函数的性能最好。Miller-Rabin wikipedia page上有伪代码

Answer 3

remove（）在总体方案中并不慢，只是代码经常调用它。在

正如dappawit建议的那样，与其修改列表，不如更改列表中的值，这样您就知道它不是一个可以使用的有效数字。在

我还看到，在生成质数集时，使用range(2,maxrange)，这是可以的，但如果下界远大于2，则没有效率。你将浪费计算时间在生成与问题空间无关的素数上。如果没有别的，请跟踪minrange和maxrange。在

原始代码的一个错误是使用range(2,maxrange)。这意味着maxrange不在考虑的数字列表中。尝试将3 5作为a和b的输入来查看bug。在

range(2,maxrange+1)解决了这个问题。在

代码中的另一个错误是修改了原始序列：

来自Python docs - for-statement

It is not safe to modify the sequence being iterated over in the loop (this can only happen for mutable sequence types, such as lists). If you need to modify the list you are iterating over (for example, to duplicate selected items) you must iterate over a copy. The slice notation makes this particularly convenient:

我的python技能还很初级，但这似乎很管用：

旧版：

primes2 = range(2,maxrange)
for i in primes:
     for j in primes2:
         if(j != i and j%i == 0):
             primes2.remove(j)

for (a,b) in indices:
    for p in primes2:
        if(a<= p and b >= p):

新增：

^{pr2}$

您还可以跳过生成质数集的步骤，直接测试这些数字，如果您要生成的质数集不重叠（没有重复工作），则可以这样做。 enter link description here