Problem: Find Prime numbers in a range

Generate all prime numbers between two given numbers.

Input:

The first line of the input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of a single line containing two space separated integers m and n.
Output:

For every test case print all prime numbers p such that m <= p <= n, space separated. Separate the answers for each test case by a new line.

Constraints:
1<=T<=60
1 <= m <= n <= 100000,
n – m <= 100000

Example:

Input:

2

1 10

3 5

Output:

2 3 5 7

3 5

My idea:
Using sieve Eratosthenes to generate a list of primes <= 100000, then just go through the list and print primes in the range
Heres the implementation in Python 2.7:

from math import sqrt
from time import time
def make_primes(): 
    """
        generate primes <= 10000
    """
    sieve_eratosthenes = [True]*100001
    bound = int(sqrt(len(sieve_eratosthenes)))
    for i in range(2, bound+1):
        if sieve_eratosthenes[i]:
            for j in range(i+i, len(sieve_eratosthenes), i):
                sieve_eratosthenes[j] = False
    return filter(lambda x: sieve_eratosthenes[x] == True, \
                range(2, len(sieve_eratosthenes)))

primes = make_primes()

def primes_in_range(n, m):
    """
        This is a generator function
        Using generator might help your program
        run faster
        n : start
        m : end
    """
    for i in range(len(primes)):
        if primes[i] >= n and primes[i] <= m:
            yield primes[i] 
        elif primes[i] > m:
            break

if __name__ == '__main__':
    make_primes()
    t = input()
    for _ in range(t):
        n, m = map(int, raw_input().split())
        for prime in primes_in_range(n, m):
            print prime,
        print

 

Advertisements