Julia（Primes）で素数判定、素因数分解する方法

どうも、木村（@kimu3_slime）です。

今回は、Julia（Primes）で素数判定、素因数分解する方法を紹介します。

準備
素数判定、素因数分解する方法
こちらもおすすめ

準備

Primes.jlを使うので、持っていなければインストールしておきましょう。

using Pkg
Pkg.add("Primes")

1 2	using Pkg Pkg.add("Primes")

準備として、以下のコードを実行しておきます。

using Primes

1	using Primes

素数判定、素因数分解する方法

「isprime(整数)」で、整数が素数かどうか、trueかfalseで返してくれます。

isprime(53)

1	isprime(53)

true

true

「factor(整数)」で、整数を素因数分解できます。

isprime(57)
factor(57)

1 2	isprime(57) factor(57)

false
3 * 19

1 2	false 3 * 19

手計算では素数判定するのが難しい大きな数でも、素早く計算してくれます。

factor(2021)
factor(202112271521)
factor(factorial(20))

factor(2021)

factor(202112271521)

factor(factorial(20))

43 * 47
11177 * 18082873
2^18 * 3^8 * 5^4 * 7^2 * 11 * 13 * 17 * 19

43 * 47

11177 * 18082873

2^18 * 3^8 * 5^4 * 7^2 * 11 * 13 * 17 * 19

大きな整数を扱うには、BigIntを使わないとオーバーフローしてしまいます。

@time factor(BigInt(2)^(100)-1)
@time factor(BigInt(2)^(120)-1)
@time factor(BigInt(2)^(150)-1)

@time factor(BigInt(2)^(100)-1)

@time factor(BigInt(2)^(120)-1)

@time factor(BigInt(2)^(150)-1)

  0.000803 seconds (8.55 k allocations: 167.742 KiB)
3 * 5^3 * 11 * 31 * 41 * 101 * 251 * 601 * 1801 * 4051 * 8101 * 268501

0.003538 seconds (52.83 k allocations: 1.008 MiB)
3^2 * 5^2 * 7 * 11 * 13 * 17 * 31 * 41 * 61 * 151 * 241 * 331 * 1321 * 61681 * 4562284561

 0.018483 seconds (277.34 k allocations: 5.383 MiB)
3^2 * 7 * 11 * 31 * 151 * 251 * 331 * 601 * 1801 * 4051 * 100801 * 10567201 * 1133836730401

0.000803 seconds (8.55 k allocations: 167.742 KiB)

3 * 5^3 * 11 * 31 * 41 * 101 * 251 * 601 * 1801 * 4051 * 8101 * 268501

0.003538 seconds (52.83 k allocations: 1.008 MiB)

3^2 * 5^2 * 7 * 11 * 13 * 17 * 31 * 41 * 61 * 151 * 241 * 331 * 1321 * 61681 * 4562284561

0.018483 seconds (277.34 k allocations: 5.383 MiB)

3^2 * 7 * 11 * 31 * 151 * 251 * 331 * 601 * 1801 * 4051 * 100801 * 10567201 * 1133836730401

大きな数ほど素因数分解には時間がかかり、現実的な時間で解けるものには限りがあります。

「primes(a,b)」は、a以上b以下の素数をベクトルとして返し、素数の一覧が得られます。

primes(1,50)

1	primes(1,50)

15-element Vector{Int64}:
  2
  3
  5
  7
 11
 13
 17
 19
 23
 29
 31
 37
 41
 43
 47

15-element Vector{Int64}:

「length(ベクトル)」でベクトルのサイズを測れば、特定の範囲にある素数の個数、数え上げの問題が解けます。

1000以下の素数は250個以下であることを示せ。
（2021年一橋大学前期第1問）

length(primes(1,1000))

1	length(primes(1,1000))

168

168

与えられた自然数\(n\)に対し、それ以下の素数の個数を返す関数（素数カウント関数）は、\(\pi(n)\)と表される数論的関数として有名です。

参考：数論的関数、乗法的関数とは何か：約数関数を例に

ディリクレの素数定理によると、\(4n+1\)、\(4n+3\)の形の等差数列は、それぞれ無限に多くの素数を含むことが知られています。これが正しいかどうか、素数判定の関数isprmeを使って、部分的に確かめてみましょう。

与えられた配列に対し、その要素が素数かどうかを判定する関数を定義します。

function arrayisprime(a)
    for i in a
        println(string(i)," ",isprime(i))
    end
end

function arrayisprime(a)

for i in a

println(string(i)," ",isprime(i))

end

これを使って、素数が含まれているか確認してみましょう。

arrayisprime([4*i+3 for i in 40:50])

1	arrayisprime([4*i+3 for i in 40:50])

163 true
167 true
171 false
175 false
179 true
183 false
187 false
191 true
195 false
199 true
203 false

163 true

167 true

171 false

175 false

179 true

183 false

187 false

191 true

195 false

199 true

203 false

arrayisprime( [4*i+3 for i in 1000:1010])

1	arrayisprime( [4*i+3 for i in 1000:1010])

4003 true
4007 true
4011 false
4015 false
4019 true
4023 false
4027 true
4031 false
4035 false
4039 false
4043 false

4003 true

4007 true

4011 false

4015 false

4019 true

4023 false

4027 true

4031 false

4035 false

4039 false

4043 false

arrayisprime([4*i+1 for i in 1000:1010])

1	arrayisprime([4*i+1 for i in 1000:1010])

4001 true
4005 false
4009 false
4013 true
4017 false
4021 true
4025 false
4029 false
4033 false
4037 false
4041 false

4001 true

4005 false

4009 false

4013 true

4017 false

4021 true

4025 false

4029 false

4033 false

4037 false

4041 false

arrayisprime( [4*i+1 for i in 10000:10010])

1	arrayisprime( [4*i+1 for i in 10000:10010])

40001 false
40005 false
40009 true
40013 true
40017 false
40021 false
40025 false
40029 false
40033 false
40037 true
40041 false

40001 false

40005 false

40009 true

40013 true

40017 false

40021 false

40025 false

40029 false

40033 false

40037 true

40041 false

trueがいくつか含まれていて、確かに無数に素数を含んでいそうですね。

以上、Julia（Primes）で素数判定、素因数分解する方法を紹介してきました。

大きな数の素数判定、素因数分解は、エラトステネスの篩（試し割り）で手計算で行うには時間がかかりすぎます。コンピュータである程度の速さで計算してくれるのは嬉しいですね。

木村すらいむ（@kimu3_slime）でした。ではでは。

1から始める Juliaプログラミング

posted with AmaQuick at 2021.10.29

進藤裕之(著), 佐藤建太(著)
コロナ社 (2020-03-26T00:00:01Z)

￥7,353 (コレクター商品)

Amazon.co.jpで詳細を見る

こちらもおすすめ

ディリクレの素数定理とは？（素数が無限に含まれる等差数列）

素数の性質：無限にあること、素因数分解の一意性と応用

素数判定の試し割り法エラトステネスの篩とは

数論的関数、乗法的関数とは何か：約数関数を例に

Julia（SymPy）で多項式の展開・因数分解、方程式を解く方法