📂ジュリア

ジュリアでの因数分解および素数関数の使用方法

概要

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)

• n=$n$に対して、オイラーのφ関数$\phi$を使用して、$\displaystyle n \prod_{p \mid n} \left( 1 - {{ 1 } \over { p }} \right)$を返す。