运行缓慢

Question

Python的素数的代码我试图解决此处提到的问题：https://www.spoj.pl/problems/PRIME1/

我也给下面的描述。

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

输入

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

输出

对于每个测试实例打印所有素数p使得m < = P < = n时，用空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 list remove很慢。我的代码是正确的，但我超过了timelimit。有人可以帮我改进这个代码。

Answer 1

除了删除不是主要元素的元素，为什么不用一些标记值替换它，可能是-1或None？然后打印时，只打印不是哨兵的值。

使用长度为(n-m)的列表，然后编号为i的索引为x[m+i]。

Answer 2

remove（）在事物的宏观方案中并不慢，只是代码将其称为LOT。

正如dappawit所建议的，不是修改列表，而是改变列表中的值，以便知道它不是一个有效的数字。

我也看到，当你生成一组素数时，你可以使用range(2,maxrange)，这是可以的，但如果下限远大于2，则效率不高。你将浪费计算时间来生成素数，甚至与问题空间有关。如果没有其他，跟踪最小范围以及最大范围。

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

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

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

从Python docs - for-statement

它是不安全的修改序列上迭代的循环（这只能发生于可变序列类型，如列表）。如果您需要修改要迭代的列表（例如，复制选定项目），则必须遍历副本。切片标志，使这个特别的方便：

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

你可以还可以跳过生成素数集并直接测试数字，如果必须基因组的数字，这将工作率素数不重叠（没有工作重复）。 enter link description here

Answer 3

素数测试功能将表现最好。有一个在Miller-Rabin wikipedia page

Answer 4

伪这里是Miller–Rabin primality test为小奇数Python中的确定性变种：

from math import log 

def isprime(n): 
    assert 1 < n < 4759123141 and n % 2 != 0, n 

    # (n-1) == 2**s * d 
    s = 0 
    d = n-1 
    while d & 1 == 0: 
     s += 1 
     d >>= 1 
    assert d % 2 != 0 and (n-1) == d*2**s 

    for a in [2, 7, 61]: 
     if not 2 <= a <= min(n-1, int(2*log(n)**2)): 
      break 
     if (pow(a, d, n) != 1 and 
      all(pow(a, d*2**r, n) != (n-1) for r in xrange(s))): 
      return False 
    return True 

代码的意图是成为一个可执行的伪代码。