Prime Sieves

The goal of a sieve is to find prime numbers without using trial division. That is, we want to be able to use only addition and multiplication.

Array-based sieve

To find all primes up to a fixed number N, we can initialize a Boolean array of size N. The value at each index indicates whether that number is prime.

On finding a new prime number p, cross out all multiples of p starting from p^2. We can start here because any smaller multiple of p will already have been crossed out by a smaller prime.

Map-based sieve

If we want to be able to extend the list of primes dynamically, we can use a map-based method instead. The keys will be composite numbers, and the values will be a list of prime divisors of the key.

Some notes on the implementation:

The prime 2 is omitted to make the algorithm run faster.
When a composite number k is found, each prime divisor p is relisted as a divisor of k+2p.
When a new prime p is found, it is listed as a candidate for p^2 rather than a smaller value. This saves a bit of time, since any smaller multiple of p will already have a smaller prime divisor.

Composite	Prime Divisors