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.
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 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 = *m arr = arr = 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>1 else range(2,n+1) for each in list_prime: firstfactor = (arr/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