奇数
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以上の素数は全て奇数ですから、
奇数のうちの素数じゃないものに規則があるということは、
素数の規則がわかったと言っても良いと思うのですが、
まあ、もともと素数生成アルゴリズムはたくさんありますね。
数学者が素数について議論していると言われますが数学者が求めている素数の規則性とはどんなものなのでしょうか?
A 回答 (2件)
- 最新から表示
- 回答順に表示
No.2
- 回答日時:
それは自明すぎる規則性ですね。
n^nから2n間隔ということはその数はn^n+2kn(kは非負整数,nは2以上の整数)であり全てnの倍数です。
#1さんのおっしゃっていることがずばりです。
LangFanさんのこの方法はエラトステネスのふるいの変形版です。
No.1
- 回答日時:
エラトステネスのふるい と呼ばれているものと大差なしでしょう。
似てますけど微妙に違いますね。
奇数だけでエラトステネスのふるいをやる+探索リストを保持しなくていい
という点があると思います。
エラトステネスのふるいと呼ばれるアルゴリズムは最初に探索リストを作成し
そこから不要なものを削除していくので、探索範囲を限定しなければいけません。
しかしこの周期性に基づくアルゴリズムは開始された周期を記録しておくリストを持ち、
そのリストに周期を追加していくだけなので上限無く探索できます。
この周期性に基づいた方法なら、
奇数列自体は自明なので記録する必要が無く、
1ビット目が3,2ビット目が5、3ビット目が7と解釈されるようなビット列を各周期毎に持ち、
登場位置のビットを立てて、
全ビット列で論理和を取り、反転させるだけで素数が求まります。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 複素関数と実関数のテーラー展開の違いについて 1 2022/08/09 06:18
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- 物理学 素数の並びと量子力学のエネルギー準位を表す数式が似ているみたいなことをNHK の番組で見た記憶がある 2 2023/08/14 22:14
- 数学 p を奇素数 ((b) は p≠5) とするとき, 以下の同値関係を示せ. (a) (-2/p) = 3 2022/07/03 16:35
- 数学 数学者は「26万分の1の確率は偶然の可能性もある」と言いますか? 1 2022/07/03 14:37
- 数学 素数について 7 2022/03/31 02:33
- 高校 述語論理の基本的な質問 3 2022/04/23 10:35
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- 数学 「素数(数の原子)」とは、「1と自分自身以外で割り切れない正の整数」でしたよね? 1 2022/04/09 23:45
- 数学 例1 明日の試合は大谷または佐々木が先発です。 明日の試合は大谷が先発または佐々木が先発です。 例2 5 2023/03/30 13:50
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
EXCELで高さ0で隠れた行の素早...
-
ワードで勝手に均等割付される
-
間隔は「開く」?「空く」?
-
一部だけ行間隔を狭めたいんです。
-
Wordのコメントのフォーマット...
-
オブジェクトどうしの間隔を設...
-
WORDで文字間隔が伸びる
-
Wordの均等割り付け 漢字とひ...
-
Wordの表(A4縦)で50行以上くら...
-
wordで改行しても次のページに...
-
Word97で目次を1ページで収める...
-
Excelの行高が突然、異常に大き...
-
ワードで罫線枠を固定したい
-
WORDで文字数、行数が指定...
-
Access レポートの文字間を設...
-
Word2007 原稿用紙のフォント...
-
Wordの行間隔の設定について 課...
-
【至急教えてください】wordの...
-
EXCEL の折り返し書式設定して...
-
Wordの数式入力で行間が広くな...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
EXCELで高さ0で隠れた行の素早...
-
間隔は「開く」?「空く」?
-
ワードで勝手に均等割付される
-
Wordのコメントのフォーマット...
-
EXCEL の折り返し書式設定して...
-
一部だけ行間隔を狭めたいんです。
-
Wordの表(A4縦)で50行以上くら...
-
市販の便箋に印刷をしたい
-
wordで改行しても次のページに...
-
WORDで文字間隔が伸びる
-
Excelの行高が突然、異常に大き...
-
オブジェクトどうしの間隔を設...
-
ワードで拡大した1文字を用紙...
-
Access レポートの文字間を設...
-
ワードで罫線枠を固定したい
-
autocad 表の行の高さ調整
-
Word2016で禁則処理がうまくゆ...
-
WORDで文字数、行数が指定...
-
ワードの文字スペースの間隔が...
-
一太郎からWordへ変換した...
おすすめ情報