prime package:arithmoi

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

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*ι]

A set of Prime integers.

how to evaluate a function on prime powers

Container for pairwise coprime numbers.

A list of pairwise coprime numbers with their multiplicities.

The input list is assumed to be a factorisation of some number into a list of powers of (possibly, composite) non-zero factors. The output list is a factorisation of the same number such that all factors are coprime. Such transformation is crucial to continue factorisation (lazily, in parallel or concurrent fashion) without having to merge multiplicities of primes, which occurs more than in one composite factor.

>>> splitIntoCoprimes [(140, 1), (165, 1)]
Coprimes {unCoprimes = [(28,1),(33,1),(5,2)]}

>>> splitIntoCoprimes [(360, 1), (210, 1)]
Coprimes {unCoprimes = [(7,1),(5,2),(3,3),(2,4)]}

Unwrap.

Unidirectional pattern for residues modulo 2p^k for odd prime p.

Unidirectional pattern for residues modulo p^k for odd prime p.

List all square roots by prime modulo.

>>> import Data.Maybe

>>> import Math.NumberTheory.Primes

>>> sqrtsModPrime 1 (fromJust (isPrime 5))
[1,4]

>>> sqrtsModPrime 0 (fromJust (isPrime 5))
[0]

>>> sqrtsModPrime 2 (fromJust (isPrime 5))
[]

List all square roots modulo the power of a prime.

>>> import Data.Maybe

>>> import Math.NumberTheory.Primes

>>> sqrtsModPrimePower 7 (fromJust (isPrime 3)) 2
[4,5]

>>> sqrtsModPrimePower 9 (fromJust (isPrime 3)) 3
[3,12,21,24,6,15]

Check whether an argument is prime. If it is then return an associated prime.

>>> isPrime (3 :: Integer)
Just (Prime 3)

>>> isPrime (4 :: Integer)
Nothing

>>> isPrime (-5 :: Integer)
Just (Prime 5)

This function is a replacement for isPrime. If you were looking for the latter, please import Math.NumberTheory.Primes.Testing instead of this module.

Smallest prime, greater or equal to argument.

nextPrime (-100) ==    2
nextPrime  1000  == 1009
nextPrime  1009  == 1009

Largest prime, less or equal to argument. Undefined, when argument < 2.

precPrime 100 == 97
precPrime  97 == 97

Convert between primes of different types, similar in spirit to toIntegralSized. A simpler version of this function is:

toPrimeIntegral :: (Integral a, Integral b) => a -> Maybe b
toPrimeIntegral (Prime a)
| toInteger a == b = Just (Prime (fromInteger b))
| otherwise        = Nothing
where
b = toInteger a

The point of toPrimeIntegral is to avoid redundant conversions and conditions, when it is safe to do so, determining type sizes statically with bitSizeMaybe. For example, toPrimeIntegral from Prime Int to Prime Word boils down to Just . fromIntegral.

Unwrap prime element.

approxPrimeCount n gives an approximation of the number of primes not exceeding n. The approximation is fairly good for n large enough.

Following property holds:

approxPrimeCount n >= primeCount n || n >= approxPrimeCountOverestimateLimit

nthPrime n calculates the n-th prime. Numbering of primes is 1-based, so nthPrime 1 == 2. Requires O((n*log n)^0.5) space, the time complexity is roughly O((n*log n)^0.7. The argument must be strictly positive.