Python prime number code running slow

I am trying to solve the problem mentioned here: https://www.spoj.pl/problems/PRIME1/

I am also giving the description below.

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.`

My code is as below. I am thinking remove method on list is very slow.

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

I think python list remove is very slow. My code is correct but I am getting timelimit exceeded. can someone help me improve this code.

A primality testing function will perform best. There's pseudocode on the Miller-Rabin wikipedia page

Instead of removing the element that is not a prime, why not replace it with some sentinel value, perhaps -1 or None? Then when printing, just print the values that aren't sentinels.

Use a list of length (n-m), and then the index for number i is x[m+i].

remove() isn't slow in the grand scheme of things, it's just that the code calls it a LOT.

As dappawit suggests, rather than modifying the list, change the value in the list so you know that it isn't a valid number to use.

I also see that when you generate the set of prime numbers, you use range(2,maxrange) which is okay, but not efficient if the lower bound is much greater than 2. You'll be wasting computing time on generating primes that aren't even relevant to the problem space. If nothing else, keep track of minrange as well as maxrange.

A bug with your original code is that you use range(2,maxrange). That means maxrange is not in the list of numbers considered. Try 3 5 as input for a and b to see the bug.

range(2,maxrange+1) fixes the problem.

Another bug in the code is that you modify the original sequence:

From 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:

My python skills are rudimentary, but this seems to work:

Old:

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

New:

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

You could also skip generating the set of prime numbers and just test the numbers directly, which would work if the sets of numbers you have to generate prime numbers are not overlapping (no work duplication). enter link description here

Here's a deterministic variant of the Miller–Rabin primality test for small odd integers in 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

The code intent is to be an executable pseudo-code.