CodeChef PRIME1 problem in Python 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
  &lt;= m &lt;= n &lt;= 1000000000, n-m&lt;=100000) separated by a space.
  
  Output
  
  For every test case print all prime numbers p such that m &lt;= p &lt;= n,
  one number per line. Separate the answers for each test case by an
  empty line.


I have used segmented sieve and my code doesn't give TLE on any CodeChef IDE etc. yet I am getting a TLE. How can I optimise this code?   

import math
max_n=10**9
m = int(math.sqrt(max_n))
arr = [1]*m
arr[0] = arr[1] = 0 
#Calculate primes upto math.sqrt(max_n)
for x in xrange(m):
    for i in xrange(2,int(x**0.5)+1):
        if x%i==0:
            arr[x]=0
            break
list_prime=[]
for i,each in enumerate(arr):
    if each==1:
        list_prime.append(i)

#sieve b/w m and n
for _ in xrange(int(raw_input().strip())):
    m,n = map(int,raw_input().split())
    arr = range(m,n+1) if m&gt;1 else range(2,n+1)
    for each in list_prime:
        firstfactor = (arr[0]/each)*each
        for x in xrange(firstfactor,n+1,each):
            try:
                if x!=each:
                    arr.remove(x)
            except:
                pass
    for each in arr:
        print each
    print
Using the same variables for different purposes in the same block of code is confusing to the reader. Split the code in 2-3 functions so that they become local variables.
You use trial division to compute the list of small primes even though you know about sieving. Sieving is faster.
arr.remove(x) in the innermost loop is slow because it scans through the whole list (to find the element to remove, and to move subsequent elements back). Use a set instead, or a list of boolean values similar to arr in the first part of the code.