Julia の Primes モジュールは，R や Python で gmp パッケージでサポートされているものと同じだ。
using Primes
素因数分解 factor(n::Integer), factor(ContainerType, n::Integer)
結果の表示法
特に指定しない場合は，数式として見やすい結果が得られる。
540 = 2^2 * 3^3 * 5
factor(540)
# 2^2 * 3^3 * 5
ベクトルとして結果を得るためには ContainerType を Vector とする。同じ素因数が複数個ある場合は，複数個数分の要素として含まれる。
factor(Vector, 540)
#=
6-element Vector{Int64}:
2
2
3
3
3
5
=#
集合として結果を得る場合は，ContainerType を Set とする。この場合は，ユニークな素因数が列挙されるだけであり，それぞれの素因数が何個あったかの情報は失われる。
factor(Set, 540)
#=
Set{Int64} with 3 elements:
5
2
3
=#
キーをソートした辞書型として結果を得るる場合は，ContainerType を DataStructures.SortedDict とする。
factor(DataStructures.SortedDict, 540)
#=
SortedDict{Int64, Int64, Base.Order.ForwardOrdering} with 3 entries:
2 => 2
3 => 3
5 => 1
=#
大きな数の素因数分解
n = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 # 7420738134810
factor(n) # 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37
factor(100000000000000000000000000007) # 53 * 827 * 2281490269444000821336497
factor(2281490269444000821336497) # 2281490269444000821336497
factor(big"2281490269444000821336497") # 2281490269444000821336497
factor() の逆関数 prodfactors()
factor() の結果を全部掛け合わすと，元の数になる。
n = 540
prod(factor(n)) # 540
prodfactors(factor(Vector, n)) # 540
prodfactors(factor(DataStructures.SortedDict, n)) # 540
prodfactors(factor(Set, n)) # 30 これは，正しい答えではない
範囲内の素数生成 primes([lo,] hi)
primes(20, 50)
#=
7-element Vector{Int64}:
23
29
31
37
41
43
47
=#
次の素数 nextprime(n::Integer, i::Integer=1; interval::Integer=1)
n より小さくない i 番目に小さい素数を返す。言い回しがまだるっこしいが，指定された数が素数だった場合，次の（1番目に小さい）素数はその数自体であるということ。
nextprime(100000000000000000000000000000) # 100000000000000000000000000319
factor(100000000000000000000000000319) # 100000000000000000000000000319
nextprime(100000000000000000000000000319) # 100000000000000000000000000319
前の素数 prevprime(n::Integer, i::Integer=1; interval::Integer=1)
n より大きくない i 番目に大きい素数
2 つ先の素数
nextprime(100000000000000000000000000000, 2) # 100000000000000000000000000379
1 つ前の素数
prevprime(100000000000000000000000000378) # 100000000000000000000000000319
i 番目の素数 prime(::Type{<:Integer}=Int, i::Integer)
100000 番目の素数は 1299709
prime(100000) # 1299709
primes() で生成される 1299709 までの素数の個数を数えれば，100000 になっていることが確認できる。
length(primes(1299709)) # 100000
素数判定 isprime(n::Integer) -> Bool
isprime(100000000000000000000000000319) # true
BigInt の場合は，確率的素数判定を行う。偽陽性率（素数ではないのに素数であると判定する率）は 0.25^reps。デフォルトでは reps = 25 なので，0.25^25 = 8.881784197001252e-16 に設定される。
isprime(x::BigInt, [reps = 25]) -> Bool
isprime(big(100000000000000000000000000319)) # true
isprime(big"100000000000000000000000000319") # true
isprime(big(100000000000000000000000000318)) # false
メルセンヌ素数判定 ismersenneprime(M::Integer; [check::Bool = true]) -> Bool
メルセンヌ数とは、2の冪よりも 1 小さい自然数、すなわち 2^n − 1（n は自然数）の形の自然数のことである。
これが素数の場合はメルセンヌ素数と呼ばれる。
ismersenneprime(2^11 - 1) # false
ismersenneprime(2^13 - 1) # true
素数の篩 primesmask([lo,], hi)
lo から hi までの数に対して，素数なら 1，合成数なら 0 の BitVector を返す。
mask = primesmask(10)
#=
10-element BitVector:
0
1
1
0
1
0
1
0
0
0
=#
mask が 1 である数を取り出す。
(1:10)[mask]
#=
4-element Vector{Int64}:
2
3
5
7
=#
ラディカル radical(n::Integer)
偶数個の素因数を持たないように選択した素因数の累積。
n = 2*2*3*7*7*7 # 4116
radical(n) # 42 = 2 * 3 * 7
factor(radical(n)) # 2 * 3 * 7
トーシエント数 totient(f::Factorization{T}) -> T
totient(n::Integer) -> Integer
オイラーのトーシエント関数（ ϕ(n); totient function) の値
m ≦ n で，gcd(m, n) == 1 つまり，m, n が互いに素であるものの数
n が 素数の場合は 1 〜 n-1 と n は互いに素であるので，ϕ(11) は 10
sum(gcd(m, 11) == 1 for m = 1:11)
totient(11) # 10
n が合成数の場合は，n - 1 より小さな値になる
sum(gcd(m, 100) == 1 for m = 1:100) # 40
totient(100) # 40
