arithmoi-0.9.0.0: Efficient basic number-theoretic functions.

Math.NumberTheory.Primes

Contents

Description

Synopsis

# Documentation

data Prime a Source #

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
 Source # Instance detailsDefined in Math.NumberTheory.Primes MethodsenumFrom :: Prime Int -> [Prime Int] #enumFromTo :: Prime Int -> Prime Int -> [Prime Int] # Source # Instance detailsDefined in Math.NumberTheory.Primes Methods Source # Instance detailsDefined in Math.NumberTheory.Primes Methods Source # Instance detailsDefined in Math.NumberTheory.Primes MethodsenumFrom :: Prime Word -> [Prime Word] # Eq a => Eq (Prime a) Source # Instance detailsDefined in Math.NumberTheory.Primes.Types Methods(==) :: Prime a -> Prime a -> Bool #(/=) :: Prime a -> Prime a -> Bool # Ord a => Ord (Prime a) Source # Instance detailsDefined in Math.NumberTheory.Primes.Types Methodscompare :: 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) Source # Instance detailsDefined in Math.NumberTheory.Primes.Types MethodsshowsPrec :: Int -> Prime a -> ShowS #show :: Prime a -> String #showList :: [Prime a] -> ShowS # Generic (Prime a) Source # Instance detailsDefined in Math.NumberTheory.Primes.Types Associated Typestype Rep (Prime a) :: Type -> Type # Methodsfrom :: Prime a -> Rep (Prime a) x #to :: Rep (Prime a) x -> Prime a # NFData a => NFData (Prime a) Source # Instance detailsDefined in Math.NumberTheory.Primes.Types Methodsrnf :: Prime a -> () # type Rep (Prime a) Source # Instance detailsDefined in Math.NumberTheory.Primes.Types type Rep (Prime a) = D1 (MetaData "Prime" "Math.NumberTheory.Primes.Types" "arithmoi-0.9.0.0-E3bSyM9N8uIFxgJyxrBJhq" True) (C1 (MetaCons "Prime" PrefixI True) (S1 (MetaSel (Just "unPrime") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)))

unPrime :: Prime a -> a Source #

Unwrap prime element.

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

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 Source #

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

precPrime 100 == 97
precPrime  97 == 97

class Num a => UniqueFactorisation a where Source #

A class for unique factorisation domains.

Methods

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

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) Source #

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
 Source # Instance detailsDefined in Math.NumberTheory.Primes Methodsfactorise :: Int -> [(Prime Int, Word)] Source # Source # Instance detailsDefined in Math.NumberTheory.Primes Methodsfactorise :: Integer -> [(Prime Integer, Word)] Source # Source # Instance detailsDefined in Math.NumberTheory.Primes Methodsfactorise :: Natural -> [(Prime Natural, Word)] Source # Source # Instance detailsDefined in Math.NumberTheory.Primes Methodsfactorise :: Word -> [(Prime Word, Word)] Source # Source # Instance details Methods Source # See the source code and Haddock comments for the factorise and isPrime functions in this module (they are not exported) for implementation details. Instance details Methods Source # Instance detailsDefined in Math.NumberTheory.Prefactored Methodsfactorise :: Prefactored a -> [(Prime (Prefactored a), Word)] Source #

# Old interface

primes :: Integral a => [Prime a] Source #

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

 Source # Instance details MethodsenumFrom :: Prime Int -> [Prime Int] #enumFromTo :: Prime Int -> Prime Int -> [Prime Int] # Source # Instance details Methods Source # Instance details Methods Source # Instance details MethodsenumFrom :: Prime Word -> [Prime Word] #