📂Julia

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 repository¹.

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 ith 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$.