prime1.py

#!/usr/bin/env python3

"""
http://www.spoj.com/problems/PRIME1/
output all primes between given pairs of numbers
"""

import sys

lines = sys.stdin.read().splitlines()
lines.remove(lines[0])                   # line 0 is the number of total input pairs. we don't need it in py

work = []
results = []

for line in lines:
    if line != '':                        # populate a list of ranges to check
        work.append(tuple(line.split(' ')))

for pair in work:
    start = int(pair[0])
    end = int(pair[1])
    primelist = [True] * (end+1)          # populate array with Trues from 0 
    primelist[0] = False                  # 0 is not a prime
    primelist[1] = False                  # 1 is not a prime
    
    for i in range(2, int(end ** 0.5)+1): # the sieve
        if primelist[i]:
            j = i ** 2 
            while j < end+1:
                primelist[j] = False
                j += i
                    
    for p in range(len(primelist)):       # even though we checked from 2 to end,
        if p < start:                     # the problem only wants primes numbers in specific ranges
            primelist[p] = False
    
    results.append(primelist)
                
for result in results:
    for n in range(len(result)):          # print any numbers marked as True
        if result[n]:
            print(n)
    if result != results[-1]:             # newlines between each set of results, but not at the end
        print()