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

Stability | experimental |

Maintainer | Sebastian Fischer (sebf@informatik.uni-kiel.de) |

This Haskell library provides an efficient lazy wheel sieve for
prime generation inspired by *Lazy wheel sieves and spirals of*
*primes* by Colin Runciman
(http://www.cs.york.ac.uk/ftpdir/pub/colin/jfp97lw.ps.gz) and
*The Genuine Sieve of Eratosthenes* by Melissa O'Neil
(http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf).

- primes :: Integral int => [int]
- wheelSieve :: Integral int => Int -> [int]
- isPrime :: Integral int => int -> Bool
- primeFactors :: Integral int => int -> [int]

# Documentation

primes :: Integral int => [int]Source

This global constant is an infinite list of prime numbers. It is
generated by a lazy wheel sieve and shared across the whole program
run. If you are concerned about the memory requirements of sharing
many primes you can call the function `wheelSieve`

directly.

This function returns an infinite list of prime numbers by sieving
with a wheel that cancels the multiples of the first `n`

primes
where `n`

is the argument given to `wheelSieve`

. Don't use too
large wheels. The number `6`

is a good value to pass to this
function. Larger wheels improve the run time at the cost of higher
memory requirements.

isPrime :: Integral int => int -> BoolSource

Checks whether a given positive number is prime.

This function uses trial division to check for divisibility with all primes below the square root of the given number. It is impractical for numbers with a very large smallest prime factor.

primeFactors :: Integral int => int -> [int]Source

Yields the sorted list of prime factors of the given positive number.

This function uses trial division and is impractical for numbers with very large prime factors.