Prime generator program SPOJ time limit exceed

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=[]

for i in xrange(int(sys.stdin.readline())):
    start,end=[int(x) for x in sys.stdin.readline().split()]
    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')

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 = []
    for _ in xrange(int(sys.stdin.readline())):
        start,end=[int(x) for x in sys.stdin.readline().split()]
        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.

StackExchange Code Review Q#46187, answer score: 7