# Problem Statement

Input

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are 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, test cases separated by an empty line.

Example

Input:

2
1 10
3 5


Output:

2
3
5
7

3
5


My Problem

I have tried very hard to optimize the code to my best, but still the online judge shows that I am exceeding the time limit. Is it possible to optimize the following code further or I should look for an alternative approach?

import sys
final=[]

if start==1:
start=2
# sieve of eras** algorithm
final.append(list(sorted(set(xrange(start,end+1)).difference(set((p * f) for p in xrange(2, int(end ** 0.5) + 2) for f in xrange(2, int(end/p) + 1))))))

# print final list items
for item1 in final:
print("\n".join([str(x) for x in item1]))
print('\n')

• The accepted answer to your previous question proposes a more efficient implementation of the sieve. Have you not tried it here? – Janne Karila Apr 3 '14 at 15:13
• I've solved a very similar problem using a double-sieve approach. – Schism Aug 11 '14 at 1:25

Re-organising the code

A quite easy thing to start with is to split the logic into a part collecting the input and a part performing computation from this input. This makes things clearer but also this might make testing easier and make some optimisations possible later on.

You can also take this chance to remove whatever is not needed :

• i is not needed, the usage is to use _ for throw-away values in Python.
• final is not needed : you populate it one element at a time and then you iterate on it to display the elements.
• You don't need to recreate a new string to call join, you can use generator expressions.

Here's what I have at this stage :

#!/usr/bin/python

import sys

if False :
# Test from standard input
inputs = []
if start==1:
start=2
inputs.append((start,end))
else:
# Hardcoded test
inputs = [(2,10),(5,7)]

for start,end in inputs:
# sieve of eras** algorithm
primes = (list(sorted(set(xrange(start,end+1)).difference(set((p * f) for p in xrange(2, int(end ** 0.5) + 2) for f in xrange(2, int(end/p) + 1))))))
print("\n".join(str(p) for p in primes)+"\n")


Now, I can use inputs = [(2,10),(5,7),(9999985,10000000),(9999937,9999987)] for performance testing.

Computing things once

At the moment, you re-compute your sieve multiple times. You might as well juste do it once with the biggest max you can find.

def sieve_of_era(n):
primes = [True]*(n+1)
primes[0] = primes[1] = False
for i in range(2, int(n**0.5)+1):
if primes[i]:
for j in range(i*i, n+1, i):
primes[j] = False
return primes

sieve = sieve_of_era(max(end for _,end in inputs))


Then, it's only a matter of collecting the information and printing it :

print "\n\n".join("\n".join(str(p) for p in xrange(start,end+1) if sieve[p]) for start,end in inputs)


A last remark

Your "sieve" considers 1 as a prime number and for that number, you added a hack to change 1 into 2 in the inputs. This is not required anymore and once it's removed, everything can be included in a single list comprehension.

The code becomes :

#!/usr/bin/python

import sys

inputs = [[int(x) for x in sys.stdin.readline().split()] for _ in xrange(int(sys.stdin.readline()))] if False else [(2,10),(5,7),(9999985,10000000),(9999937,9999987)]

def sieve_of_era(n):
primes = [True]*(n+1)
primes[0] = primes[1] = False
for i in range(2, int(n**0.5)+1):
if primes[i]:
for j in range(i*i, n+1, i):
primes[j] = False
return primes

sieve = sieve_of_era(max(end for _,end in inputs))

print "\n\n".join("\n".join(str(p) for p in xrange(start,end+1) if sieve[p]) for start,end in inputs)


I haven't tried edge cases for the sieve function but it looks ok.

• Thank you So much You solved a whole lot of my problems..:) – Akash Rana Apr 3 '14 at 14:58
• The program is producing memory error for values : 999900000 1000000000 – Akash Rana Apr 3 '14 at 16:51
• @Andres if you have code that doesn't work you could try stackoverflow.com. For very large numbers you could consider keeping a set of primes found so far, rather than a list of ALL numbers. The set of primes will be much smaller. – trichoplax Apr 8 '14 at 11:50

First, long lines make your code hard to read. The easier the code is to read, the easier it is for you to see what it does and spot potential improvements. It's also easier for others to suggest improvements to your code if it's easy for them to read it.

It is true that sometimes a one line expression can run faster than a loop over several lines, but even a one liner can be displayed over several lines by using brackets or parentheses for implicit line continuation. This still counts as a one liner from the bytecode compiler's point of view and will run just as fast. I won't point out minor spacing issues as you use spacing very readably in some parts, so I'm guessing the other parts are not lack of knowledge. There's PEP 8 if you want finer guidance on presentation, but I'm reviewing for time performance here.

I heard Eratosthenes died, no need to worry about copyright - you can use his full name in the comments. More seriously, comments are discarded before the code is compiled to bytecode and run, so you don't need to worry about shortening them. Longer comments make the file slightly larger, but they do not affect the running time at all. Full words and clear sentences are good.

# Tweaks

Small improvements to speed can be made by being aware of how Python works. For example, defining r = xrange(2, int(end ** 2) + 2) before your loop and using r inside your loop will save Python having to define the range each time through the loop (including calculating end ** 2 each time through the loop). Such fine tuning won't make much difference if you have an inefficient algorithm though.

# Algorithm

The biggest improvements in speed are very often from changing the algorithm - using a different approach rather than just tweaking the performance of the current approach There are parts of your long line (sieve of Eratosthenes algorithm) that appear to be making unnecessary extra work:

for p in xrange(2, int(end ** 0.5) + 2)


This gives you the range up to and including int(end ** 0.5) + 1), which is always more than the square root, even when considering a square number. Since you only need to check numbers which are less than or equal to the square root, I would change the + 2 to say + 1.

The major inefficiency with your algorithm is that you are checking all numbers up to the square root, rather than all prime numbers up to the square root. To see why this is unnecessary, consider that when you remove all multiples of 4, they have already been removed when you removed all multiples of 2. Then the same when you remove all multiples of 6, all multiples of 8, and so on. The same thing happens again with multiples of 6, 9, 12 because you have already removed all multiples of 3. With large numbers this will cause a huge amount of repetition - creating and taking differences of sets which already have no elements in common, and repeating this unnecessary step huge numbers of times.

For this reason it is well worth your time to think about how you could only remove multiples of prime numbers. The extra time your program takes keeping a list of prime numbers already found will save you so much time over the course of the run that you will see a very significant speed up for large numbers.