Prime number functions

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.

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

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])

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

primes([lo,] hi)

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

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

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

prime(::Type{<:Integer}=Int, i::Integer)

The i-th prime number.

julia> prime(1)
2

julia> prime(3)
5

isprime(n::Integer) -> Bool

Returns true if n is prime, and false otherwise.

julia> isprime(3)
true

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

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

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.

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

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.

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)).

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[]

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.