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.
