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

## 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; interval::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`.

If `interval` is provided, primes are sought in increments of `interval`. This can be useful to ensure the presence of certain divisors in `p-1`. The range of possible values for `interval` is currently `1:typemax(Int)`.

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

julia> nextprime(5)
5

julia> nextprime(4, 2)
7

julia> nextprime(5, 2)
7

julia> nextprime(2^10+1; interval=1024)
12289

julia> gcd(12289 - 1, 1024) # 1024 | p - 1
1024``````
source
``prevprime(n::Integer, i::Integer=1; interval::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`.

If `interval` is provided, primes are sought in increments of `interval`. This can be useful to ensure the presence of certain divisors in `p-1`. The range of possible values for `interval` is currently `1:typemax(Int)`.

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

## Number-theoretic functions

``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
``totient(f::Factorization{T}) -> T``

Compute the Euler totient function of the number whose prime factorization is given by `f`. This method may be preferable to `totient(::Integer)` when the factorization can be reused for other purposes.

source
``totient(n::Integer) -> Integer``

Compute the Euler totient function \$ϕ(n)\$, which counts the number of positive integers less than or equal to \$n\$ that are relatively prime to \$n\$ (that is, the number of positive integers `m ≤ n` with `gcd(m, n) == 1`). The totient function of `n` when `n` is negative is defined to be `totient(abs(n))`.

source