NumberSieves-0.0: Number Theoretic Sieves: primes, factorization, and Euler's Totient

NumberTheory.Sieve.Factor

Description

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.

Synopsis

# Documentation

Instances

 Eq FactorSieve Ord FactorSieve Show FactorSieve

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.