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 list remove 非常慢。我的代码是正确的，但我超出了时间限制。谁能帮我改进这段代码。

Answer 1

素数测试函数将表现最佳。 Miller-Rabin wikipedia page 上有伪代码