この素数の規則性は既知ですか？

奇数
1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51
奇数のうち素数じゃないものには分かりやすい規則性がある
3^3から始まり3x2間隔
5^5から始まり5x2間隔
7^7から始まり7x2間隔
9^7から始まり9x2間隔
つまりn番目の周期の開始位置が(2n+1)^2で、
間隔が2(2n+1)なのです。
この周期に基づき素数判定プログラムを書いてみましたが、２万くらいまで調べても正しく動作しました。
（信頼されている素数判定プログラムと同じ結果を返しました）

この規則性は既知でしょうか？
３以上の素数は全て奇数ですから、
奇数のうちの素数じゃないものに規則があるということは、
素数の規則がわかったと言っても良いと思うのですが、
まあ、もともと素数生成アルゴリズムはたくさんありますね。
数学者が素数について議論していると言われますが数学者が求めている素数の規則性とはどんなものなのでしょうか？

No.1 回答者： takafiro974 回答日時： 2012/12/19 05:55

エラトステネスのふるい　と呼ばれているものと大差なしでしょう。

この回答へのお礼

似てますけど微妙に違いますね。
奇数だけでエラトステネスのふるいをやる＋探索リストを保持しなくていい
という点があると思います。
エラトステネスのふるいと呼ばれるアルゴリズムは最初に探索リストを作成し
そこから不要なものを削除していくので、探索範囲を限定しなければいけません。
しかしこの周期性に基づくアルゴリズムは開始された周期を記録しておくリストを持ち、
そのリストに周期を追加していくだけなので上限無く探索できます。

この周期性に基づいた方法なら、
奇数列自体は自明なので記録する必要が無く、
１ビット目が３，２ビット目が５、３ビット目が７と解釈されるようなビット列を各周期毎に持ち、
登場位置のビットを立てて、
全ビット列で論理和を取り、反転させるだけで素数が求まります。

お礼日時：2012/12/19 07:27

No.2 回答者： windwald 回答日時： 2012/12/19 07:54

それは自明すぎる規則性ですね。

n^nから2n間隔ということはその数はn^n＋2kn(kは非負整数,nは2以上の整数)であり全てnの倍数です。

#1さんのおっしゃっていることがずばりです。
LangFanさんのこの方法はエラトステネスのふるいの変形版です。