2 (PRIME1) - Prime Generator
Given an interval where and , find all prime numbers in that interval.
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 . However, no composite number less than or equal to will have both factors greater than , 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.
2 1 10 3 5
2 3 5 7 3 5