Optimised Python Code gives TLE for PRIME1

Question

PRIME1 is a codechef problem which states:

Shridhar 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 first line contains t, the number of test cases (less then or equal to 10). Followed by t lines which contain 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. Separate the answers for each test case by an empty line.

I have optimised my code according to suggestions given here. But, my edits were rolled back when I tried to post my optimised code. So, I am still getting a TLE error and I don't understand why. Help me optimise this code further:

import math
def sieve_basic_list(list_prime):
    max_n=10**9
    m = int(math.sqrt(max_n))
    lim = int(math.sqrt(m))+1
    arr = [True]*(m+1)
    arr[0]=arr[1]=False

    #Calculate primes upto m only so loop runs sqrt(m) times.
    for x in xrange(2,lim):
        if arr[x]==False:
            continue
        for i in xrange(x*x,m+1,x):
            arr[i]=False
    for i,each in enumerate(arr):
        if each:
            list_prime.append(i)

def mnsieve(list_prime):
    #program tc input and mnrange calc
    for _ in xrange(int(raw_input().strip())):
        m,n = map(int,raw_input().split())
        mnrange = [True]*(n-m+1)
        mnrange[0] = False if m==1 else True
        for each in list_prime:
            firstfactor = ((m-1)/each)*each #firstfactor nearest to m i.e firstfactor-m gives index
            for x in xrange(firstfactor,n+1,each):
                try:
                    if x not in list_prime:
                        mnrange[x-m]=False
                except:
                    pass
        for i,each in enumerate(mnrange):
            if each:
                print i+m
        print

list_prime=[]
sieve_basic_list(list_prime)
mnsieve(list_prime)

Answer 1

Finally, I solved the problem. And these suggestions helped. Here is the final solution:

import math
def sieve_basic_list(list_prime):
    max_n=10**9
    m = int(math.sqrt(max_n))
    lim = int(math.sqrt(m))+1
    arr = [True]*(m+1)
    arr[0]=arr[1]=False

    #Calculate primes upto m only so loop runs sqrt(m) times.
    for x in xrange(2,lim):
        if arr[x]==False:
            continue
        for i in xrange(x*x,m+1,x):
            arr[i]=False
    for i,each in enumerate(arr):
        if each:
            list_prime.add(i)

def mnsieve(list_prime):
    #program tc input and mnrange calc
    for _ in xrange(int(raw_input().strip())):
        m,n = map(int,raw_input().split())
        mnrange = [True]*(n-m+1)
        mnrange[0] = False if m==1 else True
        for each in list_prime:
            if each <= int(n**0.5): #important optmisation
                firstfactor = ((m-1)/each)*each #firstfactor nearest to m i.e firstfactor-m gives index
                for x in xrange(firstfactor,n+1,each):
                        if x!=each and x-m >= 0: #x-m can become -ve and that is disastorous in python lists!
                            mnrange[x-m]=False
       for i,each in enumerate(mnrange):
            if each:
                print i+m
       print

list_prime=set([]) #important optimisation
sieve_basic_list(list_prime)
mnsieve(list_prime)

Check it here: on codechef