How to Use Factorization and Prime Number Functions in Julia
Overview
Primes.jl
is a package that deals with functions related to primes and prime factorization. The implementation of functions related to analytic number theory is still lacking.
This is not a comprehensive list of all the features of the package, but rather a selection of the useful ones. For more details, check the repository1.
Types
Prime Factorization Primes.Factorization
julia> factor(12)
2^2 * 3
julia> factor(12)[1]
0
julia> factor(12)[2]
2
julia> factor(12)[3]
1
julia> factor(12)[4]
0
Prime factorization uses a unique data type that differentiates between base and exponent. Accessing a base as an index allows you to reference its exponent.
Functions
Generating Primes prime()
, primes()
julia> using Primes
julia> prime(4)
7
julia> primes(10)
4-element Vector{Int64}:
2
3
5
7
prime(::Type{<:Integer}=Int, i::Integer)
- Returns the
i
th prime.
primes([lo,] hi)
- Returns an array of primes up to
hi
.
Prime Testing isprime()
julia> isprime(7)
true
julia> isprime(8)
false
isprime(n::Integer)
- Returns a boolean indicating whether
n
is a prime. This function’s implementation uses the Miller-Rabin primality test among others.
Prime Factorization factor()
julia> factor(24)
2^3 * 3
julia> factor(Vector, 24)
4-element Vector{Int64}:
2
2
2
3
julia> factor(Array, 24)
4-element Vector{Int64}:
2
2
2
3
julia> factor(Set, 24)
Set{Int64} with 2 elements:
2
3
factor(n::Integer) -> Primes.Factorization
factor(ContainerType, n::Integer) -> ContainerType
- Returns the prime factorization of
n
. The implementation of this function uses the Pollard’s $p-1$ rho algorithm among others. - If
ContainerType
is provided, it returns the result in the specified container, otherwise, it returns in its own data type,Primes.Factorization
.
Euler’s Totient Function
julia> totient(12)
4
totient(n::Integer)
- For
n
=$n$, returns $\displaystyle n \prod_{p \mid n} \left( 1 - {{ 1 } \over { p }} \right)$ using Euler’s totient function $\phi$.