prime -package:primes

Not on Stackage, so not searched. prime number tools

Wrapper for prime elements of a. It is supposed to be constructed by nextPrime / precPrime. and eliminated by unPrime. One can leverage Enum instance to generate lists of primes. Here are some examples.

• Generate primes from the given interval:

>>> :set -XFlexibleContexts

>>> [nextPrime 101 .. precPrime 130]
[Prime 101,Prime 103,Prime 107,Prime 109,Prime 113,Prime 127]

• Generate an infinite list of primes:

[nextPrime 101 ..]
[Prime 101,Prime 103,Prime 107,Prime 109,Prime 113,Prime 127...

• Generate primes from the given interval of form p = 6k+5:

>>> [nextPrime 101, nextPrime 107 .. precPrime 150]
[Prime 101,Prime 107,Prime 113,Prime 131,Prime 137,Prime 149]

• Get next prime:

>>> succ (nextPrime 101)
Prime 103

• Get previous prime:

>>> pred (nextPrime 101)
Prime 97

• Count primes less than a given number (cf. approxPrimeCount):

>>> fromEnum (precPrime 100)
25

• Get 25-th prime number (cf. nthPrimeApprox):

>>> toEnum 25 :: Prime Int
Prime 97

Identifier ends in Integer many primes.

Deprecated: This module is a perpetual draft and will therefore be removed from xmonad-contrib in the near future.

A Prime is a function that transforms an XConfig. It's not a monad, but we turn on RebindableSyntax so we can abuse the pretty do notation.

Module for finding the greatest prime number that is less than or equal to a given number

Like primElemRepSizeB but assumes pointers/words are 8 words wide. This can be useful to compute the size of a rep as if we were compiling for a 64bit platform.

The prime prefix; primePrefix mempty == mempty for monoids.

The prime suffix; primeSuffix mempty == mempty for monoids.

Ascending list of primes.

>>> take 10 primes
[Prime 2,Prime 3,Prime 5,Prime 7,Prime 11,Prime 13,Prime 17,Prime 19,Prime 23,Prime 29]

primes is a polymorphic list, so the results of computations are not retained in memory. Make it monomorphic to take advantages of memoization. Compare

>>> primes !! 1000000 :: Prime Int -- (5.32 secs, 6,945,267,496 bytes)
Prime 15485867

>>> primes !! 1000000 :: Prime Int -- (5.19 secs, 6,945,267,496 bytes)
Prime 15485867

against

>>> let primes' = primes :: [Prime Int]

>>> primes' !! 1000000 :: Prime Int -- (5.29 secs, 6,945,269,856 bytes)
Prime 15485867

>>> primes' !! 1000000 :: Prime Int -- (0.02 secs, 336,232 bytes)
Prime 15485867

primeCount n == π(n) is the number of (positive) primes not exceeding n. For efficiency, the calculations are done on 64-bit signed integers, therefore n must not exceed primeCountMaxArg. Requires O(n^0.5) space, the time complexity is roughly O(n^0.7). For small bounds, primeCount n simply counts the primes not exceeding n, for bounds from 30000 on, Meissel's algorithm is used in the improved form due to D.H. Lehmer, cf. http://en.wikipedia.org/wiki/Prime_counting_function#Algorithms_for_evaluating_.CF.80.28x.29.

Maximal allowed argument of primeCount. Currently 8e18.

An infinite list of Eisenstein primes. Uses primes in Z to exhaustively generate all Eisenstein primes in order of ascending norm.

• Every prime is in the first sextant, so the list contains no associates.
• Eisenstein primes from the whole complex plane can be generated by applying associates to each prime in this list.

>>> take 10 primes
[Prime 2+ω,Prime 2,Prime 3+2*ω,Prime 3+ω,Prime 4+3*ω,Prime 4+ω,Prime 5+3*ω,Prime 5+2*ω,Prime 5,Prime 6+5*ω]

An infinite list of the Gaussian primes. Uses primes in Z to exhaustively generate all Gaussian primes (up to associates), in order of ascending magnitude.

>>> take 10 primes
[Prime 1+ι,Prime 2+ι,Prime 1+2*ι,Prime 3,Prime 3+2*ι,Prime 2+3*ι,Prime 4+ι,Prime 1+4*ι,Prime 5+2*ι,Prime 2+5*ι]

Get the name of the equality type.

primEraseEquality : {a : Level} {A : Set a} {x y : A} -> x ≡ y -> x ≡ y

The prime numbers. Implemented with the algorithm in:

• Colin Runciman (1997) Lazy Wheel Sieves and Spirals of Primes, Functional Pearl, Journal of Functional Programming, 7(2). pp.219--225. ISSN 0956-7968 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7096