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
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:
for i,each in enumerate(arr):
    if each==1:

#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[0]/each)*each
        for x in xrange(firstfactor,n+1,each):
                if x!=each:
    for each in arr:
        print each

2 Answers 2

  • 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.

This is not an efficient implementation of segmented sieve.

First, you are finding the prime numbers up to sqrt(nmax) by trial division. You should use the sieve of Eratosthenes instead.

for x in xrange(m):
    if arr[x]==0:
    for i in xrange(x*x,m+1,x):

You can now use a similar Boolean array for the segmented sieve as well.

arr = [1] * (n-m+1)
for each in list_prime:
    firstfactor = max((m-1)/each+1,2)*each
    for x in xrange(firstfactor,n+1,each):

Just output the nonzero elements in arr and you are done.

  • 1
    \$\begingroup\$ I think it will be 'continue' instead of 'break' in the upper code. Further, the second code will not generate all prime nos if (m,n) overlaps with (1,sqrt(10^9)) for eg. firstfactor for 2 will be 2 itself if (m,n) is (2,x). Hence arr[2-2]=0 and 2 will not be considered a prime. \$\endgroup\$ Apr 5, 2017 at 14:35
  • \$\begingroup\$ Thanks for pointing out, is it fixed now? \$\endgroup\$ Apr 5, 2017 at 17:26
  • \$\begingroup\$ No, it's not fixed completely yet. The upper code too is bugged. Think about how many times the outer loop will run. \$\endgroup\$ Apr 6, 2017 at 11:46
  • \$\begingroup\$ The overall complexity will be m log log m where m = sqrt(nmax), I don't see the problem. \$\endgroup\$ Apr 6, 2017 at 12:07
  • \$\begingroup\$ It can be optimised because it needs to run only sqrt(m) times. Plus there are multiple bugs in your lower code. Now that I have solved the problem, I can see. \$\endgroup\$ Apr 6, 2017 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.