Portability | Non-portable (GHC extensions) |
---|---|
Stability | Provisional |
Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |
Prime generation using a sieve. Currently, an enhanced sieve of Eratosthenes is used, switching to an Atkin sieve is planned (if I get around to implementing it and it's not slower).
The sieve used is segmented, with a chunk size chosen to give good (enough)
cache locality while still getting something substantial done per chunk.
However, that means we must store data for primes up to the square root of
where sieving is done, thus sieving primes up to n
requires
O(sqrt n/log n)
space.
- primes :: [Integer]
- sieveFrom :: Integer -> [Integer]
- data PrimeSieve
- primeSieve :: Integer -> PrimeSieve
- psieveList :: [PrimeSieve]
- psieveFrom :: Integer -> [PrimeSieve]
- primeList :: PrimeSieve -> [Integer]
Documentation
List of primes.
Since the sieve uses unboxed arrays, overflow occurs at some point,
but not before 10^6*
(I forgot where exactly).
fromIntegral
(maxBound
:: Int
)
data PrimeSieve Source
Compact store of primality flags.
primeSieve :: Integer -> PrimeSieveSource
Sieve primes up to (and including) a bound. For small enough bounds, this is more efficient than using the segmented sieve.
Since arrays are Int
-indexed, overflow occurs when the sieve
size comes near
, that corresponds to an
upper bound near maxBound
:: Int
15/8*
. On maxBound
32
-bit systems, that
is often within memory limits, so don't give bounds larger than
8*10^9
there.
psieveList :: [PrimeSieve]Source
List of primes in the form of a list of PrimeSieve
s, more compact than
primes
, thus it may be better to use
than keeping the list of primes alive during the entire run.
psieveList
>>= primeList
psieveFrom :: Integer -> [PrimeSieve]Source
creates the list of psieveFrom
nPrimeSieve
s starting roughly
at n
. Due to the organisation of the sieve, the list may contain
a few primes less than n
.
This form uses less memory than [
, hence it may be preferable
to use this if it is to be reused.
Integer
]
primeList :: PrimeSieve -> [Integer]Source
Generate a list of primes for consumption from a
PrimeSieve
.