| Portability | portable |
|---|---|
| Stability | experimental |
| Maintainer | Sebastian Fischer (sebf@informatik.uni-kiel.de) |
| Safe Haskell | Safe-Inferred |
Data.Numbers.Primes
Description
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.
Arguments
| :: Integral int | |
| => Int | number of primes canceled by the wheel |
| -> [int] | infinite list of primes |
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.