Python质数代码运行缓慢

Question

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

下面是问题的描述。

彼得想为他的加密系统生成一些质数。帮帮他吧！你的任务是生成两个给定数字之间的所有质数！

输入

输入的第一行是测试案例的数量 t（t<=10）。接下来的 t 行中，每行有两个数字 m 和 n（1 <= m <= n <= 1000000000，n-m<=100000），用空格分开。

输出

对于每个测试案例，打印所有满足 m <= p <= n 的质数 p，每个质数占一行，测试案例之间用空行分隔。

我的代码如下。我觉得在列表上使用 remove 方法非常慢。

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 的列表 remove 方法很慢。我的代码是正确的，但我遇到了超时的问题。有人能帮我改进这段代码吗？

Answer 1

remove() 在整体上并不慢，只是代码调用它的次数太多了。

正如 dappawit 所建议的，不如不直接修改列表，而是把列表中的值改成一个无效的数字，这样你就知道这个数字不可以用了。

我还注意到，当你生成素数的时候，你用的是 range(2,maxrange)，这没问题，但如果下限远大于 2，就不太高效了。这样会浪费计算时间去生成那些对你问题没有帮助的素数。如果没有别的，至少要同时记录下 minrange 和 maxrange。

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

用 range(2,maxrange+1) 可以解决这个问题。

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

来自 Python 文档 - for 语句

在循环中修改正在迭代的序列是不安全的（这只会发生在可变序列类型，比如列表）。如果你需要修改正在迭代的列表（例如，复制选定的项目），你必须对一个副本进行迭代。切片表示法使这特别方便：

我的 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):

新的：

primes2 = array.array('L', range(minrange,maxrange+1))
for i in primes:
    for j in primes2:
        if(j != i and j%i == 0):
            primes2[j-minrange] = 0

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

你也可以跳过生成素数的步骤，直接测试数字，这样做如果你需要生成的素数集合没有重叠（没有重复工作）就可以。

点击这里查看链接描述

Answer 2

一个质数测试函数的表现会非常好。你可以在Miller-Rabin的维基百科页面上找到伪代码。

Answer 3

与其把不是质数的元素删掉，不如用一个特殊的值来替换它，比如说 -1 或者 None。这样在打印的时候，只需要打印那些不是特殊值的元素就可以了。

可以用一个长度为 (n-m) 的列表，然后对于数字 i，它在列表中的位置就是 x[m+i]。