Prime number functions

Prime factorization

Primes.eachfactorFunction

eachfactor(n::Integer)->FactorIterator Returns a lazy iterator of factors of n in (factor, multiplicity) pairs. This can be very useful for computing multiplicitive functions since for small numbers (eg numbers with no factor >2^16), allocating the storage required for factor(n) can introduce significant overhead.

source
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 for values in the range of an INT64 variable: true if n is prime, and false otherwise for bigger values: true if n is probably prime, and false otherwise (false-positive rate = 0.25^reps with reps=25 –> considerered safe)

More detailed:
for even numbers: returns deterministic and correct results
for values in the range of an  INT64 variable: returns deterministic and correct results (by Lookup-tables, trial-division, Miller-Rabin, Lucas-Test)
for bigger values: returns probabilistic resultsfrom GNU Multiple Precision Arithmetic Library
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).

isprobablyprime is inherited from the module IntegerMathUtils that provides a wrapper to access functionality from the GNU Multiple Precision Arithmetic Library (GMP) library

julia> isprime(big(3))
true
source
Primes.ismersenneprimeFunction
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
Primes.divisorsFunction
divisors(n::Integer) -> Vector

Return a vector with the positive divisors of n.

For a nonzero integer n with prime factorization n = p₁^k₁ ⋯ pₘ^kₘ, divisors(n) returns a vector of length (k₁ + 1)⋯(kₘ + 1) containing the divisors of n in lexicographic (rather than numerical) order.

divisors(-n) is equivalent to divisors(n).

For convenience, divisors(0) returns [].

Example

julia> divisors(60)
12-element Vector{Int64}:
  1         # 1
  2         # 2
  4         # 2 * 2
  3         # 3
  6         # 3 * 2
 12         # 3 * 2 * 2
  5         # 5
 10         # 5 * 2
 20         # 5 * 2 * 2
 15         # 5 * 3
 30         # 5 * 3 * 2
 60         # 5 * 3 * 2 * 2

julia> divisors(-10)
4-element Vector{Int64}:
  1
  2
  5
 10

julia> divisors(0)
Int64[]
source
divisors(f::Factorization) -> Vector

Return a vector with the positive divisors of the number whose factorization is f. Divisors are sorted lexicographically, rather than numerically.

source