primes- Efficient, purely functional generation of prime numbers

MaintainerSebastian Fischer (
Safe HaskellSafe-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 ( and The Genuine Sieve of Eratosthenes by Melissa O'Neil (



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.



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