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

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

How to Factorization in julia

개요

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

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

타입

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


  1. https://github.com/JuliaMath/Primes.jl ↩︎

댓글