締切済み

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

  • 困ってます
  • 質問No.7851658
  • 閲覧数1676
  • ありがとう数2
  • 気になる数2
  • 回答数2
  • コメント数0

お礼率 19% (19/99)

奇数
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)なのです。
この周期に基づき素数判定プログラムを書いてみましたが、2万くらいまで調べても正しく動作しました。
(信頼されている素数判定プログラムと同じ結果を返しました)

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

回答 (全2件)

  • 回答No.2

ベストアンサー率 29% (610/2083)

それは自明すぎる規則性ですね。
n^nから2n間隔ということはその数はn^n+2kn(kは非負整数,nは2以上の整数)であり全てnの倍数です。

#1さんのおっしゃっていることがずばりです。
LangFanさんのこの方法はエラトステネスのふるいの変形版です。
Be MORE 7・12 OK-チップでイイコトはじまる
  • 回答No.1

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

お礼率 19% (19/99)

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

この周期性に基づいた方法なら、
奇数列自体は自明なので記録する必要が無く、
1ビット目が3,2ビット目が5、3ビット目が7と解釈されるようなビット列を各周期毎に持ち、
登場位置のビットを立てて、
全ビット列で論理和を取り、反転させるだけで素数が求まります。
投稿日時 - 2012-12-19 07:27:47
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する

特集


より良い社会へ。感謝経済プロジェクト始動

ピックアップ

ページ先頭へ