Data.Numbers.Primes

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

Documentation

primes :: Integral int => [int]

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.

wheelSieve

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

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]

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.