Portability | portable |
---|---|

Stability | experimental |

Maintainer | leon@melding-monads.com |

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.

- data FactorSieve
- findFactor :: Integral a => FactorSieve -> a -> a
- sieveBound :: Integral a => FactorSieve -> a
- isPrime :: Integral a => FactorSieve -> a -> Bool
- factor :: Integral a => FactorSieve -> a -> [(a, a)]
- sieve :: Integral a => a -> FactorSieve

# Documentation

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

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

sieveBound :: Integral a => FactorSieve -> aSource

Returns the upper limit of a sieve.

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

Is a number prime?

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

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

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

sieve :: Integral a => a -> FactorSieveSource

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