ジュリアでの因数分解および素数関数の使用方法
概要
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)
n
=$n$に対して、オイラーのφ関数$\phi$を使用して、$\displaystyle n \prod_{p \mid n} \left( 1 - {{ 1 } \over { p }} \right)$を返す。