📂줄리아

줄리아에서 소인수분해 및 소수관련 함수 사용하는 법

개요

Primes.jl은 소수에 관련된 함수 및 소인수분해를 다루는 패키지다. 해석적 정수론에 관련된 함수에 대한 구현은 아직 미비한 편이다.

패키지의 모든 기능을 정리한 것은 아니고 유용할만한 것만 추렸으니 자세한 것은 리파지터리를 확인하자¹.

타입

소인수분해 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(), 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)

• i번째 소수를 리턴한다.

primes([lo,] hi)

• hi까지의 소수들의 배열을 리턴한다.

소수판정 isprime()

julia> isprime(7)
true

julia> isprime(8)
false

isprime(n::Integer)

• n이 소수인지 판별한 결과를 불리언으로 리턴한다. 이 함수의 구현에는 밀러-라빈 판정법 등이 사용되었다.

소인수분해 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

• n의 소인수분해를 리턴한다. 이 함수의 구현에는 폴라드 $p-1$ 소인수분해 알고리즘 등이 사용되었다.
• ContainerType을 주면 해당 컨테이너에 맞게 리턴하고, 따로 주지 않으면 자체 자료형인 Primes.Factorization으로 리턴한다.

오일러 토션트 함수

julia> totient(12)
4

totient(n::Integer)

• 오일러 토션트 함수 $\phi$로, n=$n$ 에 대해 $\displaystyle n \prod_{p \mid n} \left( 1 - {{ 1 } \over { p }} \right)$ 를 리턴한다.