Math.NumberTheory.Primes

Documentation

data Prime a

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:

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

>>> prec (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

Instances

Bounded (Prime Int)

Defined in Math.NumberTheory.Primes

Methods

minBound :: Prime Int

maxBound :: Prime Int

Bounded (Prime Word)

Defined in Math.NumberTheory.Primes

Methods

minBound :: Prime Word

maxBound :: Prime Word

Enum (Prime Int)

Defined in Math.NumberTheory.Primes

Methods

succ :: Prime Int -> Prime Int

pred :: Prime Int -> Prime Int

toEnum :: Int -> Prime Int

fromEnum :: Prime Int -> Int

enumFrom :: Prime Int -> [Prime Int]

enumFromThen :: Prime Int -> Prime Int -> [Prime Int]

enumFromTo :: Prime Int -> Prime Int -> [Prime Int]

enumFromThenTo :: Prime Int -> Prime Int -> Prime Int -> [Prime Int]

Enum (Prime Integer)

Defined in Math.NumberTheory.Primes

Methods

succ :: Prime Integer -> Prime Integer

pred :: Prime Integer -> Prime Integer

toEnum :: Int -> Prime Integer

fromEnum :: Prime Integer -> Int

enumFrom :: Prime Integer -> [Prime Integer]

enumFromThen :: Prime Integer -> Prime Integer -> [Prime Integer]

enumFromTo :: Prime Integer -> Prime Integer -> [Prime Integer]

enumFromThenTo :: Prime Integer -> Prime Integer -> Prime Integer -> [Prime Integer]

Enum (Prime Natural)

Defined in Math.NumberTheory.Primes

Methods

succ :: Prime Natural -> Prime Natural

pred :: Prime Natural -> Prime Natural

toEnum :: Int -> Prime Natural

fromEnum :: Prime Natural -> Int

enumFrom :: Prime Natural -> [Prime Natural]

enumFromThen :: Prime Natural -> Prime Natural -> [Prime Natural]

enumFromTo :: Prime Natural -> Prime Natural -> [Prime Natural]

enumFromThenTo :: Prime Natural -> Prime Natural -> Prime Natural -> [Prime Natural]

Enum (Prime Word)

Defined in Math.NumberTheory.Primes

Methods

succ :: Prime Word -> Prime Word

pred :: Prime Word -> Prime Word

toEnum :: Int -> Prime Word

fromEnum :: Prime Word -> Int

enumFrom :: Prime Word -> [Prime Word]

enumFromThen :: Prime Word -> Prime Word -> [Prime Word]

enumFromTo :: Prime Word -> Prime Word -> [Prime Word]

enumFromThenTo :: Prime Word -> Prime Word -> Prime Word -> [Prime Word]

Eq a => Eq (Prime a)

Defined in Math.NumberTheory.Primes.Types

Methods

(==) :: Prime a -> Prime a -> Bool

(/=) :: Prime a -> Prime a -> Bool

Ord a => Ord (Prime a)

Defined in Math.NumberTheory.Primes.Types

Methods

compare :: Prime a -> Prime a -> Ordering

(<) :: Prime a -> Prime a -> Bool

(<=) :: Prime a -> Prime a -> Bool

(>) :: Prime a -> Prime a -> Bool

(>=) :: Prime a -> Prime a -> Bool

max :: Prime a -> Prime a -> Prime a

min :: Prime a -> Prime a -> Prime a

Show a => Show (Prime a)

Defined in Math.NumberTheory.Primes.Types

Methods

showsPrec :: Int -> Prime a -> ShowS

show :: Prime a -> String

showList :: [Prime a] -> ShowS

Generic (Prime a)

Defined in Math.NumberTheory.Primes.Types

Associated Types

type Rep (Prime a) :: Type -> Type

Methods

from :: Prime a -> Rep (Prime a) x

to :: Rep (Prime a) x -> Prime a

NFData a => NFData (Prime a)

Defined in Math.NumberTheory.Primes.Types

Methods

rnf :: Prime a -> ()

type Rep (Prime a)

Defined in Math.NumberTheory.Primes.Types

type Rep (Prime a) = D1 (MetaData "Prime" "Math.NumberTheory.Primes.Types" "arithmoi-0.11.0.1-IKjojSflRPr5K8Oqr9EaCh" True) (C1 (MetaCons "Prime" PrefixI True) (S1 (MetaSel (Just "unPrime") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)))

unPrime :: Prime a -> a

Unwrap prime element.

nextPrime :: (Bits a, Integral a, UniqueFactorisation a) => a -> Prime a

Smallest prime, greater or equal to argument.

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

precPrime :: (Bits a, Integral a, UniqueFactorisation a) => a -> Prime a

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

precPrime 100 == 97
precPrime  97 == 97

class Num a => UniqueFactorisation a where

A class for unique factorisation domains.

Methods

factorise :: a -> [(Prime a, Word)]

Factorise a number into a product of prime powers. Factorisation of 0 is an undefined behaviour. Otherwise following invariants hold:

abs n == abs (product (map (\(p, k) -> unPrime p ^ k) (factorise n)))
all ((> 0) . snd) (factorise n)

>>> factorise (1 :: Integer)
[]
>>> factorise (-1 :: Integer)
[]
>>> factorise (6 :: Integer)
[(Prime 2,1),(Prime 3,1)]
>>> factorise (-108 :: Integer)
[(Prime 2,2),(Prime 3,3)]

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

Warning: there are no guarantees of any particular order of prime factors, do not expect them to be ascending. E. g.,

>>> factorise 10251562501
[(Prime 101701,1),(Prime 100801,1)]

isPrime :: a -> Maybe (Prime a)

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.

Instances

UniqueFactorisation Int

Defined in Math.NumberTheory.Primes

Methods

factorise :: Int -> [(Prime Int, Word)]

isPrime :: Int -> Maybe (Prime Int)

UniqueFactorisation Integer

Defined in Math.NumberTheory.Primes

Methods

factorise :: Integer -> [(Prime Integer, Word)]

isPrime :: Integer -> Maybe (Prime Integer)

UniqueFactorisation Natural

Defined in Math.NumberTheory.Primes

Methods

factorise :: Natural -> [(Prime Natural, Word)]

isPrime :: Natural -> Maybe (Prime Natural)

UniqueFactorisation Word

Defined in Math.NumberTheory.Primes

Methods

factorise :: Word -> [(Prime Word, Word)]

isPrime :: Word -> Maybe (Prime Word)

UniqueFactorisation GaussianInteger

Defined in Math.NumberTheory.Quadratic.GaussianIntegers

Methods

factorise :: GaussianInteger -> [(Prime GaussianInteger, Word)]

isPrime :: GaussianInteger -> Maybe (Prime GaussianInteger)

UniqueFactorisation EisensteinInteger

See the source code and Haddock comments for the factorise and isPrime functions in this module (they are not exported) for implementation details.

Defined in Math.NumberTheory.Quadratic.EisensteinIntegers

Methods

factorise :: EisensteinInteger -> [(Prime EisensteinInteger, Word)]

isPrime :: EisensteinInteger -> Maybe (Prime EisensteinInteger)

(Eq a, GcdDomain a, UniqueFactorisation a) => UniqueFactorisation (Prefactored a)

Defined in Math.NumberTheory.Prefactored

Methods

factorise :: Prefactored a -> [(Prime (Prefactored a), Word)]

isPrime :: Prefactored a -> Maybe (Prime (Prefactored a))

factorBack :: Num a => [(Prime a, Word)] -> a

Restore a number from its factorisation.

Old interface

primes :: Integral a => [Prime a]

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

>>> :set +s
>>> primes !! 1000000 :: Prime Int
Prime 15485867
(5.32 secs, 6,945,267,496 bytes)
>>> primes !! 1000000 :: Prime Int
Prime 15485867
(5.19 secs, 6,945,267,496 bytes)

against

>>> let primes' = primes :: [Prime Int]
>>> primes' !! 1000000 :: Prime Int
Prime 15485867
(5.29 secs, 6,945,269,856 bytes)
>>> primes' !! 1000000 :: Prime Int
Prime 15485867
(0.02 secs, 336,232 bytes)

Orphan instances

Bounded (Prime Int)

Methods

minBound :: Prime Int

maxBound :: Prime Int

Bounded (Prime Word)

Methods

minBound :: Prime Word

maxBound :: Prime Word

Enum (Prime Int)

Methods

succ :: Prime Int -> Prime Int

pred :: Prime Int -> Prime Int

toEnum :: Int -> Prime Int

fromEnum :: Prime Int -> Int

enumFrom :: Prime Int -> [Prime Int]

enumFromThen :: Prime Int -> Prime Int -> [Prime Int]

enumFromTo :: Prime Int -> Prime Int -> [Prime Int]

enumFromThenTo :: Prime Int -> Prime Int -> Prime Int -> [Prime Int]

Enum (Prime Integer)

Methods

succ :: Prime Integer -> Prime Integer

pred :: Prime Integer -> Prime Integer

toEnum :: Int -> Prime Integer

fromEnum :: Prime Integer -> Int

enumFrom :: Prime Integer -> [Prime Integer]

enumFromThen :: Prime Integer -> Prime Integer -> [Prime Integer]

enumFromTo :: Prime Integer -> Prime Integer -> [Prime Integer]

enumFromThenTo :: Prime Integer -> Prime Integer -> Prime Integer -> [Prime Integer]

Enum (Prime Natural)

Methods

succ :: Prime Natural -> Prime Natural

pred :: Prime Natural -> Prime Natural

toEnum :: Int -> Prime Natural

fromEnum :: Prime Natural -> Int

enumFrom :: Prime Natural -> [Prime Natural]

enumFromThen :: Prime Natural -> Prime Natural -> [Prime Natural]

enumFromTo :: Prime Natural -> Prime Natural -> [Prime Natural]

enumFromThenTo :: Prime Natural -> Prime Natural -> Prime Natural -> [Prime Natural]

Enum (Prime Word)

Methods

succ :: Prime Word -> Prime Word

pred :: Prime Word -> Prime Word

toEnum :: Int -> Prime Word

fromEnum :: Prime Word -> Int

enumFrom :: Prime Word -> [Prime Word]

enumFromThen :: Prime Word -> Prime Word -> [Prime Word]

enumFromTo :: Prime Word -> Prime Word -> [Prime Word]

enumFromThenTo :: Prime Word -> Prime Word -> Prime Word -> [Prime Word]