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

Stability | experimental |

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

Safe Haskell | Safe-Infered |

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 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.