SPOJ PRIME1

From Algorithmist
Jump to navigation Jump to search

2 (PRIME1) - Prime Generator[edit]

Summary[edit]

Given an interval where and , find all prime numbers in that interval.

Explanation[edit]

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.

Input[edit]

2
1 10
3 5

Output[edit]

2
3
5
7

3
5

Solution[edit]

Code : http://www.shawonruet.com/2016/10/spoj-prime1-prime-generator.html