arithmoi-0.12.1.0: Efficient basic number-theoretic functions.

Copyright | (c) 2016-2018 Andrew.Lelechenko
License | MIT
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell | Safe-Inferred
Language | Haskell2010

Math.NumberTheory.Primes

Contents

- Old interface
- Orphan instances

Description

Synopsis

- data Prime a
- unPrime :: Prime a -> a
- toPrimeIntegral :: (Integral a, Integral b, Bits a, Bits b) => Prime a -> Maybe (Prime b)
- nextPrime :: (Bits a, Integral a, UniqueFactorisation a) => a -> Prime a
- precPrime :: (Bits a, Integral a, UniqueFactorisation a) => a -> Prime a
- class Num a => UniqueFactorisation a where
  - factorise :: a -> [(Prime a, Word)]
  - isPrime :: a -> Maybe (Prime a)
- factorBack :: Num a => [(Prime a, Word)] -> a
- primes :: Integral a => [Prime a]

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

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

#### Instances

Instances details

Vector Vector a => Vector Vector (Prime a) Source # |

Instance details

Defined in Math.NumberTheory.Primes.Types

Methods

basicUnsafeFreeze :: Mutable Vector s (Prime a) -> ST s (Vector (Prime a)) Source #

basicUnsafeThaw :: Vector (Prime a) -> ST s (Mutable Vector s (Prime a)) Source #

basicLength :: Vector (Prime a) -> Int Source #

basicUnsafeSlice :: Int -> Int -> Vector (Prime a) -> Vector (Prime a) Source #

basicUnsafeIndexM :: Vector (Prime a) -> Int -> Box (Prime a) Source #

basicUnsafeCopy :: Mutable Vector s (Prime a) -> Vector (Prime a) -> ST s () Source #

elemseq :: Vector (Prime a) -> Prime a -> b -> b Source #

MVector MVector a => MVector MVector (Prime a) Source # |

Instance details

Defined in Math.NumberTheory.Primes.Types

Methods

basicLength :: MVector s (Prime a) -> Int Source #

basicUnsafeSlice :: Int -> Int -> MVector s (Prime a) -> MVector s (Prime a) Source #

basicOverlaps :: MVector s (Prime a) -> MVector s (Prime a) -> Bool Source #

basicUnsafeNew :: Int -> ST s (MVector s (Prime a)) Source #

basicInitialize :: MVector s (Prime a) -> ST s () Source #

basicUnsafeReplicate :: Int -> Prime a -> ST s (MVector s (Prime a)) Source #

basicUnsafeRead :: MVector s (Prime a) -> Int -> ST s (Prime a) Source #

basicUnsafeWrite :: MVector s (Prime a) -> Int -> Prime a -> ST s () Source #

basicClear :: MVector s (Prime a) -> ST s () Source #

basicSet :: MVector s (Prime a) -> Prime a -> ST s () Source #

basicUnsafeCopy :: MVector s (Prime a) -> MVector s (Prime a) -> ST s () Source #

basicUnsafeMove :: MVector s (Prime a) -> MVector s (Prime a) -> ST s () Source #

basicUnsafeGrow :: MVector s (Prime a) -> Int -> ST s (MVector s (Prime a)) Source #

Bounded (Prime Int) Source # |
Instance details Defined in Math.NumberTheory.Primes Methods minBound :: Prime Int Source # maxBound :: Prime Int Source #
Bounded (Prime Word) Source # |
Instance details Defined in Math.NumberTheory.Primes Methods minBound :: Prime Word Source # maxBound :: Prime Word Source #
Enum (Prime Integer) Source # |

Instance details

Defined in Math.NumberTheory.Primes

Methods

succ :: Prime Integer -> Prime Integer Source #

pred :: Prime Integer -> Prime Integer Source #

toEnum :: Int -> Prime Integer Source #

fromEnum :: Prime Integer -> Int Source #

enumFrom :: Prime Integer -> [Prime Integer] Source #

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

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

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

Enum (Prime Natural) Source # |

Instance details

Defined in Math.NumberTheory.Primes

Methods

succ :: Prime Natural -> Prime Natural Source #

pred :: Prime Natural -> Prime Natural Source #

toEnum :: Int -> Prime Natural Source #

fromEnum :: Prime Natural -> Int Source #

enumFrom :: Prime Natural -> [Prime Natural] Source #

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

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

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

Enum (Prime Int) Source # |

Instance details

Defined in Math.NumberTheory.Primes

Methods

succ :: Prime Int -> Prime Int Source #

pred :: Prime Int -> Prime Int Source #

toEnum :: Int -> Prime Int Source #

fromEnum :: Prime Int -> Int Source #

enumFrom :: Prime Int -> [Prime Int] Source #

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

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

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

Enum (Prime Word) Source # |

Instance details

Defined in Math.NumberTheory.Primes

Methods

succ :: Prime Word -> Prime Word Source #

pred :: Prime Word -> Prime Word Source #

toEnum :: Int -> Prime Word Source #

fromEnum :: Prime Word -> Int Source #

enumFrom :: Prime Word -> [Prime Word] Source #

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

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

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

Generic (Prime a) Source # |
Instance details Defined in Math.NumberTheory.Primes.Types Associated Types type Rep (Prime a) :: Type -> Type Source # Methods from :: Prime a -> Rep (Prime a) x Source # to :: Rep (Prime a) x -> Prime a Source #
Show a => Show (Prime a) Source # |
Instance details Defined in Math.NumberTheory.Primes.Types Methods showsPrec :: Int -> Prime a -> ShowS Source # show :: Prime a -> String Source # showList :: [Prime a] -> ShowS Source #
NFData a => NFData (Prime a) Source # |
Instance details Defined in Math.NumberTheory.Primes.Types Methods rnf :: Prime a -> () Source #
Eq a => Eq (Prime a) Source # |
Instance details Defined in Math.NumberTheory.Primes.Types Methods (==) :: Prime a -> Prime a -> Bool Source # (/=) :: Prime a -> Prime a -> Bool Source #
Ord a => Ord (Prime a) Source # |
Instance details Defined in Math.NumberTheory.Primes.Types Methods compare :: Prime a -> Prime a -> Ordering Source # (<) :: Prime a -> Prime a -> Bool Source # (<=) :: Prime a -> Prime a -> Bool Source # (>) :: Prime a -> Prime a -> Bool Source # (>=) :: Prime a -> Prime a -> Bool Source # max :: Prime a -> Prime a -> Prime a Source # min :: Prime a -> Prime a -> Prime a Source #
Unbox a => Unbox (Prime a) Source # |
Instance details Defined in Math.NumberTheory.Primes.Types
newtype MVector s (Prime a) Source # |
Instance details Defined in Math.NumberTheory.Primes.Types newtype MVector s (Prime a) = MV_Prime (MVector s a)
type Rep (Prime a) Source # |
Instance details Defined in Math.NumberTheory.Primes.Types type Rep (Prime a) = D1 ('MetaData "Prime" "Math.NumberTheory.Primes.Types" "arithmoi-0.12.1.0-2jRn8d5fCqUGg6rALbYqXG" 'True) (C1 ('MetaCons "Prime" 'PrefixI 'True) (S1 ('MetaSel ('Just "unPrime") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)))
newtype Vector (Prime a) Source # |
Instance details Defined in Math.NumberTheory.Primes.Types newtype Vector (Prime a) = V_Prime (Vector a)

unPrime :: Prime a -> a Source #

Unwrap prime element.

toPrimeIntegral :: (Integral a, Integral b, Bits a, Bits b) => Prime a -> Maybe (Prime b) Source #

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`.

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

Instances details

UniqueFactorisation EisensteinInteger 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 Defined in Math.NumberTheory.Quadratic.EisensteinIntegers Methods factorise :: EisensteinInteger -> [(Prime EisensteinInteger, Word)] Source # isPrime :: EisensteinInteger -> Maybe (Prime EisensteinInteger) Source #
UniqueFactorisation GaussianInteger Source # |
Instance details Defined in Math.NumberTheory.Quadratic.GaussianIntegers Methods factorise :: GaussianInteger -> [(Prime GaussianInteger, Word)] Source # isPrime :: GaussianInteger -> Maybe (Prime GaussianInteger) Source #
UniqueFactorisation Integer Source # |
Instance details Defined in Math.NumberTheory.Primes Methods factorise :: Integer -> [(Prime Integer, Word)] Source # isPrime :: Integer -> Maybe (Prime Integer) Source #
UniqueFactorisation Natural Source # |
Instance details Defined in Math.NumberTheory.Primes Methods factorise :: Natural -> [(Prime Natural, Word)] Source # isPrime :: Natural -> Maybe (Prime Natural) Source #
UniqueFactorisation Int Source # |
Instance details Defined in Math.NumberTheory.Primes Methods factorise :: Int -> [(Prime Int, Word)] Source # isPrime :: Int -> Maybe (Prime Int) Source #
UniqueFactorisation Word Source # |
Instance details Defined in Math.NumberTheory.Primes Methods factorise :: Word -> [(Prime Word, Word)] Source # isPrime :: Word -> Maybe (Prime Word) Source #
(Eq a, GcdDomain a, UniqueFactorisation a) => UniqueFactorisation (Prefactored a) Source # |
Instance details Defined in Math.NumberTheory.Prefactored Methods factorise :: Prefactored a -> [(Prime (Prefactored a), Word)] Source # isPrime :: Prefactored a -> Maybe (Prime (Prefactored a)) Source #

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

Restore a number from its factorisation.

# 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

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

# Orphan instances

Bounded (Prime Int) Source # |
Instance details Methods minBound :: Prime Int Source # maxBound :: Prime Int Source #
Bounded (Prime Word) Source # |
Instance details Methods minBound :: Prime Word Source # maxBound :: Prime Word Source #
Enum (Prime Integer) Source # |

Instance details

Methods

succ :: Prime Integer -> Prime Integer Source #

pred :: Prime Integer -> Prime Integer Source #

toEnum :: Int -> Prime Integer Source #

fromEnum :: Prime Integer -> Int Source #

enumFrom :: Prime Integer -> [Prime Integer] Source #

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

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

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

Enum (Prime Natural) Source # |

Instance details

Methods

succ :: Prime Natural -> Prime Natural Source #

pred :: Prime Natural -> Prime Natural Source #

toEnum :: Int -> Prime Natural Source #

fromEnum :: Prime Natural -> Int Source #

enumFrom :: Prime Natural -> [Prime Natural] Source #

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

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

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

Enum (Prime Int) Source # |

Instance details

Methods

succ :: Prime Int -> Prime Int Source #

pred :: Prime Int -> Prime Int Source #

toEnum :: Int -> Prime Int Source #

fromEnum :: Prime Int -> Int Source #

enumFrom :: Prime Int -> [Prime Int] Source #

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

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

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

Enum (Prime Word) Source # |

Instance details

Methods

succ :: Prime Word -> Prime Word Source #

pred :: Prime Word -> Prime Word Source #

toEnum :: Int -> Prime Word Source #

fromEnum :: Prime Word -> Int Source #

enumFrom :: Prime Word -> [Prime Word] Source #

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

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

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