Safe Haskell | None |
---|---|

Language | Haskell98 |

`AUTHOR`

- Dr. Alistair Ward
`DESCRIPTION`

- Generates the constant, conceptually infinite, list of
*prime-numbers*, using the*Sieve of Eratosthenes*; http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. - Based on http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf.
- The implementation;
has been optimised using a
*wheel*of static, but parameterised, size; is polymorphic, but with a specialisation for type`Int`

.

`CAVEAT`

- The
`Int`

-specialisation is implemented by a*rewrite-rule*, which is*very*fragile.

- sieveOfEratosthenes :: Integral i => NPrimes -> [i]

# Types

## Type-synonyms

# Functions

sieveOfEratosthenes :: Integral i => NPrimes -> [i] Source

- A refinement of the
*Sieve Of Eratosthenes*, which pre-sieves candidates, selecting only those*coprime*to the specified short sequence of low prime-numbers. - The short sequence of initial primes are represented by a
`PrimeWheel`

, of parameterised, but static, size; http://en.wikipedia.org/wiki/Wheel_factorization. - The algorithm requires one to record multiples of previously discovered primes, allowing
*composite*candidates to be eliminated by comparison. - Because each
*list*of multiples, starts with the*square*of the prime from which it was generated, the vast majority will be larger than the maximum prime ultimately demanded, and the effort of constructing and storing this list, is consequently wasted. Many implementations solve this, by requiring specification of the maximum prime required, thus allowing the construction of redundant lists of multiples to be avoided. - This implementation doesn't impose that constraint, leaving a requirement for
*rapid*storage, which is supported by*appending*the*list*of prime-multiples, to a*queue*. If a large enough candidate is ever generated, to match the*head*of the*list*of prime-multiples, at the*head*of this*queue*, then the whole*list*of prime-multiples is dropped from the*queue*, but the*tail*of this*list*of prime-multiples, for which there is now a high likelyhood of a subsequent match, must now be re-recorded. A*queue*doesn't support efficient random*insertion*, so a`Map`

is used for these subsequent multiples. This solution is faster than just using a Data.PQueue.Min. - CAVEAT: has linear
*O(n)*space-complexity.