<p>我试图解决这里提到的问题:<a href="https://www.spoj.pl/problems/PRIME1/" rel="nofollow">https://www.spoj.pl/problems/PRIME1/</a></p>
<p>我也给出了下面的描述。在</p>
<blockquote>
<p>Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!</p>
<p>Input</p>
<p>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.</p>
<p>Output</p>
<p>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.`</p>
</blockquote>
<p>我的代码如下。我认为删除列表上的方法很慢。在</p>
<pre><code>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.<a href="https://www.cnpython.com/list/append" class="inner-link">append</a>((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
</code></pre>
<p>我认为python<a href="https://www.cnpython.com/list/pop" class="inner-link">列表删除</a>非常慢。我的代码是正确的,但我已经超过了时间限制。有人能帮我改进这个代码吗。在</p>
<p>素性测试函数的性能最好。<a href="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test" rel="nofollow" title="Miller Rabin wikipedia page">Miller-Rabin wikipedia page</a>上有伪代码</p>