chinese_remainder_theorem(array::Array{Int64}, remainder::Array{Int64}))

The Chinese remainder theorem is based on simultaneous congruence. In more detail, if x knows the remainder of the Euclidean division of an array[i] by several integers, then x can determine the remainder of the division of array[i] by the product of these integers uniquely, following the condition that the divisors are pairwise coprime. For more information see: https://en.wikipedia.org/wiki/Chineseremaindertheorem

Arguments

• array::Array{Int64}: Array with elements.
• remainder::Array{Int64}: Number of elements

Examples

julia> import ClassicAlgorithmsCollections
julia> num = [3, 4, 5]
julia> rem = [2, 3, 1]
julia> ClassicAlgorithmsCollections.chinese_remainder_theorem(num, rem)
11

euler_totient(n::Int64)

Compute the positive integers up to a given integer n that are relatively prime to n; also known as Euler's totient. For more information see: https://en.wikipedia.org/wiki/Euler%27stotientfunction

Arguments

• n::Int64: Number of elements

Examples

julia> import ClassicAlgorithmsCollections
julia> ClassicAlgorithmsCollections.euler_totient(20)
[1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8]

modular_exponentiation(base::Int64, exponent::Int64, modulus::Int64)

Compute the residuum of the base raised to the exponent, which is divided by the modulus.

Arguments

• base::Int64: base
• exponent::Int64: exponent
• modulus ::Int64: modulus

Examples

julia> import ClassicAlgorithmsCollections
julia> ClassicAlgorithmsCollections.modular_exponentiation(2, 3, 15)
8

modular_inverse(base::Int64, modulus::Int64)

Compute the multiplicative inverse of the base under the modulus.

Arguments

• base::Int64: base
• modulus ::Int64: modulus

Examples

julia> import ClassicAlgorithmsCollections
julia> ClassicAlgorithmsCollections.modular_inverse(3, 11)
4

sieve_of_eratosthenes(n::Int64)

The Sieve of Eratosthenes is one of the historical algorithms dedicated to finding all prime numbers up to any given limit. The algorithm is split into four steps:

1. Create a list of sequential integers from 2 to n.
2. Define initially p=2 as the first prime number.
3. Reconstruct all multiple combinations from p=2.
4. Find the first number greater than p in the array that is not listed. Then decided:

* If no number exists => stop. 
* `p` becomes equal to the number and go back to step 3.

For more information see: https://en.wikipedia.org/wiki/SieveofEratosthenes

Arguments

• n::Int64: Number of elements

Examples

julia> import ClassicAlgorithmsCollections
julia> ClassicAlgorithmsCollections.sieve_of_eratosthenes(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]