Shridhar wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers.
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.
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=arr=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 = 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)