# SPOJ PRIME1

## Summary

Given an interval ${\displaystyle [m,n]}$ where ${\displaystyle 1\leq m\leq n\leq 10^{9}}$ and ${\displaystyle n-m\leq 100000}$, find all prime numbers in that interval.

## Explanation

This is a modification of the standard Sieve of Eratosthenes. It would be highly inefficient, using up far too much memory and time, to run the standard sieve all the way up to ${\displaystyle n}$. However, no composite number less than or equal to ${\displaystyle n}$ will have both factors greater than ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$, so we only need to know all primes up to this limit, which is no greater than 31622 (square root of 109). This is accomplished with a sieve. Then, for each query, we sieve through only the range given, using our pre-computed table of primes to eliminate composite numbers.

## Input

2
1 10
3 5


## Output

2
3
5
7

3
5