# Optimised Python Code gives TLE for PRIME1

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)

• I'd recommend you to re-read Janne Karila's third point, as you changed it to something as bad. – Peilonrayz Apr 5 '17 at 14:56
• If you want to keep this approach, at least change list_prime=[] to list_prime=set([]) and list_prime.append(i) to list_prime.add(i). That alone will give you quite the speed improvement. I'd consider re-writing it, though. – ChatterOne Apr 5 '17 at 15:08
• @Peilonrayz Why so? I'm no longer removing an element by searching and then shifting the rest because I don't use remove() anymore. – mradul dubey Apr 5 '17 at 19:48

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:

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