Module

Data.ModularArithmetic.Primality

Package: purescript-modular-arithmetic
Repository: hdgarrood/purescript-modular-arithmetic

#primeFactors Source

primeFactors :: Int -> List Int

Find prime factors by trial division; first attempting to divide by 2 and then by every odd number after that. This is the most basic prime factorisation algorithm possible but it is more than enough for this case (specifically, when the input is guaranteed to be no more than 2^31).

Prime factors are returned in increasing order. For example:

> trialDivision 12
(2 : 2 : 3 : Nil)

Passing in any number less than 2 will return an empty list.

> trialDivision (-12)
Nil

For all positive integers, the following properties are satisfied:

> product (primeFactors n) == n
> all isPrime (primeFactors n)

#isPrime Source

isPrime :: Int -> Boolean

Check if a number is prime. Note that 1 is not a prime number.

#Prime Source

class (Pos m) <= Prime m

This class specifies that a type-level integer is prime; that is, it has exactly 2 divisors: itself, and 1.

All primes up to 100 have instances. For larger primes, you will need to use the reifyPrime function.

Instances

#reifyPrime Source

reifyPrime :: forall r. Int -> (forall p. Prime p => p -> r) -> Maybe r

Reify a prime number at the type level. If the first argument provided is not prime, this function returns Nothing.

Modules: Data.ModularArithmetic; Data.ModularArithmetic.Primality