Julia(Primes)で素数判定、素因数分解する方法

どうも、木村(@kimu3_slime)です。

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

 

準備

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

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

 

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

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

 

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

 

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

 

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

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

 

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

 

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

1000以下の素数は250個以下であることを示せ。

(2021年一橋大学 前期第1問)

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

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

 

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

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

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

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

 

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

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

木村すらいむ(@kimu3_slime)でした。ではでは。

 

1から始める Juliaプログラミング
進藤 裕之(著), 佐藤 建太(著)
コロナ社 (2020-03-26T00:00:01Z)
5つ星のうち4.5
¥7,353 (コレクター商品)

 

こちらもおすすめ

ディリクレの素数定理とは?(素数が無限に含まれる等差数列)

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

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

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

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