primes-0.2.1.0: Efficient, purely functional generation of prime numbers

Portability portable experimental Sebastian Fischer (sebf@informatik.uni-kiel.de) Safe-Infered

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

Synopsis

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