Functions

Prime number functions

Prime factorization

Primes.factorFunction.
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
Primes.prodfactorsFunction.
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.primesFunction.
primes([lo,] hi)

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

source
Primes.nextprimeFunction.
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
Primes.prevprimeFunction.
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
Primes.primeFunction.
prime(::Type{<:Integer}=Int, i::Integer)

The i-th prime number.

julia> prime(1)
2

julia> prime(3)
5
source

Identifying prime numbers

Primes.isprimeFunction.
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
Primes.primesmaskFunction.
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

Primes.radicalFunction.
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
Primes.totientFunction.
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