現代、素数判定法として採用されている方法はリュカ-レーマーテストと呼ばれている方法が一般的のようです。この方法は GIMPS にも採用されています。
リュカ-レーマーテストとはどんな判定方法かを簡素に書いてみると、下記のようになりますかね。
・ある整数 $ n $ が大きな素数であれば、巨大数 ( これを仮に $ M_n $ としましょう ) $ 2^n – 1 $ も素数であるかどうかを調べる。
この判定方法は以前にもご紹介したメルセンス数がもとになっています。ウィキペディアより
メルセンヌ数とは
$ M_n = 2^n − 1 $ が素数ならば n もまた素数であるが、逆は成立しない。素数であるメルセンヌ数をメルセンヌ素数(メルセンヌそすう、英: Mersenne prime)という。
でしたね。ですから逆は成立しない、とは言え $ n $ が素数であれば $ M_n $ も素数である事が期待は出来るところに目を付けています。
片っ端から整数をエラトステネスのふるいに掛けるよりは、素数と期待できる $ M_n $ に目を付けたほうが効率がいいですからね。
またエラトステネスのふるいよりも現在では効率の良い方法があるようです。 レーマーの定理を利用した方法で素数かどうかを判定できるようで
「$ M_n $ が素数となるのは $ M_n $ が $ M_n $ が $ S_{n-2} $ を割り切るとき、かつそのときに限る」
と言えるのだそうです。
ここで $ S_{n-2} $ はリュカ-レーマー数列とよばれるもので $ S_0 = 4 $ 、$ S_{m+1} = {S_m}^2 -2 $ ( $ m $ は自然数 ) です。
応援してね。
千里の道も一歩から。そしてその道は登り坂です。ローマは1日にして成らず、です。
| ★ 習慣作りのための、小さな課題 | ☆ 実施状況 |
|---|---|
| 斜め懸垂1回 (ボルダリングの体力獲得) 学習の気分転換 |
斜め懸垂14回 |
| そろばんの練習5問 (暗算の獲得) 数学の学習前 |
加減算 1~100の足し算 1回、1~100の引き算 1回 乗算 せず |
| 数学の問題 1問 (物理学の数式の理解力の獲得) 90分 |
チャート式 数学 白II+B:できず
チャート式 数学 青I+A:できず
数学の答え合わせは後でまとめてやる:機会なし
1.5時間 机から離れず、パソコンの画面も見ずに数学の学習に取り組む:機会なし
|
| 規則正しい生活 基本習慣 |
昨日・夜食は、食パン1枚とノンカフェインドリンクを楽しむ:〇 昨日・寝床に入った時間:23時38分 今朝・7時に布団から出る:7時14分 朝 — ブログの投稿 — |