Optimised Python Code gives TLE for PRIME1
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 &lt;= 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 &gt;= 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