Math.Sieve.Factor

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.

Documentation

data FactorSieve

Instances

Eq FactorSieve

Ord FactorSieve

Show FactorSieve

findFactor :: Integral a => FactorSieve -> a -> a

Returns the smallest prime divisor of a given number in the sieve.

sieveBound :: Integral a => FactorSieve -> a

Returns the upper limit of a sieve.

isPrime :: Integral a => FactorSieve -> a -> Bool

Is a number prime?

factor :: Integral a => FactorSieve -> a -> [(a, a)]

Factors a number completely using a sieve, e.g.

 factor (sieve 1000) 360 == [(2,3),(3,2),(5,1)]

sieve :: (Show a, Integral a) => a -> FactorSieve

Finds the smallest prime divisor of every number up to a given limit.