This is an array-based generalization of the Sieve of Eratosthenes that associates a prime divisor to each number in the sieve. This is useful if you want to factor a large quantity of small numbers
This code contains two simple optimizations: even numbers are not
represented in the array, reducing both time and space by 50%.
Secondly, the smallest prime divisor is sieved, and the prime numbers
are represented by
0 in the array instead of themselves. This allows
the divisors to be stored in half the number of bits, reducing space
consumption by another 50%.
Currently, this sieve is limited to numbers less than 2^32, and consumes one byte per number in the sieve on average. Thus if you want to find the smallest divisor of every number up to 2^32, you will need 4 GB of storage.
Returns the smallest prime divisor of a given number in the sieve.
Factors a number completely using a sieve, e.g.
factor (sieve 1000) 360 == [(2,3),(3,2),(5,1)]