# SPOJ PRIME1

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 10^{9}). 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