Functions

# Prime number functions

## Prime factorization

``factor(n::Integer) -> Primes.Factorization``

Compute the prime factorization of an integer `n`. The returned object, of type `Factorization`, is an associative container whose keys correspond to the factors, in sorted order. The value associated with each key indicates the multiplicity (i.e. the number of times the factor appears in the factorization).

``````julia> factor(100)
2^2 ⋅ 5^2``````

For convenience, a negative number `n` is factored as `-1*(-n)` (i.e. `-1` is considered to be a factor), and `0` is factored as `0^1`:

``````julia> factor(-9)
-1 ⋅ 3^2

julia> factor(0)
0

julia> collect(factor(0))
1-element Array{Pair{Int64,Int64},1}:
0=>1``````
source
``factor(ContainerType, n::Integer) -> ContainerType``

Return the factorization of `n` stored in a `ContainerType`, which must be a subtype of `AbstractDict` or `AbstractArray`, a `Set`, or an `BitSet`.

``````julia> factor(DataStructures.SortedDict, 100)
DataStructures.SortedDict{Int64,Int64,Base.Order.ForwardOrdering} with 2 entries:
2 => 2
5 => 2``````

When `ContainerType <: AbstractArray`, this returns the list of all prime factors of `n` with multiplicities, in sorted order.

``````julia> factor(Vector, 100)
4-element Array{Int64,1}:
2
2
5
5

julia> prod(factor(Vector, 100)) == 100
true``````

When `ContainerType == Set`, this returns the distinct prime factors as a set.

``````julia> factor(Set, 100)
Set([2,5])``````
source
``prodfactors(factors)``

Compute `n` (or the radical of `n` when `factors` is of type `Set` or `BitSet`) where `factors` is interpreted as the result of `factor(typeof(factors), n)`. Note that if `factors` is of type `AbstractArray` or `Primes.Factorization`, then `prodfactors` is equivalent to `Base.prod`.

``````julia> prodfactors(factor(100))
100``````
source
``radical(n::Integer)``

Compute the radical of `n`, i.e. the largest square-free divisor of `n`. This is equal to the product of the distinct prime numbers dividing `n`.

``````julia> radical(2*2*3)
6``````
source

## Generating prime numbers

``primes([lo,] hi)``

Returns a collection of the prime numbers (from `lo`, if specified) up to `hi`.

source
``nextprime(n::Integer, i::Integer=1)``

The `i`-th smallest prime not less than `n` (in particular, `nextprime(p) == p` if `p` is prime). If `i < 0`, this is equivalent to prevprime(n, -i). Note that for `n::BigInt`, the returned number is only a pseudo-prime (the function `isprime` is used internally). See also `prevprime`.

``````julia> nextprime(4)
5

julia> nextprime(5)
5

julia> nextprime(4, 2)
7

julia> nextprime(5, 2)
7``````
source
``prevprime(n::Integer, i::Integer=1)``

The `i`-th largest prime not greater than `n` (in particular `prevprime(p) == p` if `p` is prime). If `i < 0`, this is equivalent to `nextprime(n, -i)`. Note that for `n::BigInt`, the returned number is only a pseudo-prime (the function `isprime` is used internally). See also `nextprime`.

``````julia> prevprime(4)
3

julia> prevprime(5)
5

julia> prevprime(5, 2)
3``````
source
``prime(::Type{<:Integer}=Int, i::Integer)``

The `i`-th prime number.

``````julia> prime(1)
2

julia> prime(3)
5
``````
source

## Identifying prime numbers

``isprime(n::Integer) -> Bool``

Returns `true` if `n` is prime, and `false` otherwise.

``````julia> isprime(3)
true``````
source
``isprime(x::BigInt, [reps = 25]) -> Bool``

Probabilistic primality test. Returns `true` if `x` is prime with high probability (pseudoprime); and `false` if `x` is composite (not prime). The false positive rate is about `0.25^reps`. `reps = 25` is considered safe for cryptographic applications (Knuth, Seminumerical Algorithms).

``````julia> isprime(big(3))
true``````
source
``ismersenneprime(M::Integer; [check::Bool = true]) -> Bool``

Lucas-Lehmer deterministic test for Mersenne primes. `M` must be a Mersenne number, i.e. of the form `M = 2^p - 1`, where `p` is a prime number. Use the keyword argument `check` to enable/disable checking whether `M` is a valid Mersenne number; to be used with caution. Return `true` if the given Mersenne number is prime, and `false` otherwise.

``````julia> ismersenneprime(2^11 - 1)
false

julia> ismersenneprime(2^13 - 1)
true``````
source
``primesmask([lo,] hi)``

Returns a prime sieve, as a `BitArray`, of the positive integers (from `lo`, if specified) up to `hi`. Useful when working with either primes or composite numbers.

source