素数探索
★素数探索
素数探索のアルゴリズムを思いついたのでここに記す。
※自分で思いついたが、凡人の俺が思いつくくらいなので
※既に名のある有名なアルゴリズム、あるいはその劣化バージョンにだと思われる
※ググってないのでこのアルゴリズムの名前とかは分からない
●アルゴリズム概要
見つかった素数とそれ以下の素数の倍数でない数を導出する式(kn+d)を使い次の素数を求める
●アルゴリズム説明
2は素数なので
2n+0 (2の倍数)
2n+1 (2の倍数でない)
[n=0,1,2,3, ...]
と正数全体を分けられる
従って 2 の次にくる素数は 2の倍数でない式
2n+1
の1つの式で 2より大きい数の中で最小の数 である
ここで n=0 において 2より大きい数の中で最小の数 である 3 が見つかり 3 は素数である
ここで 2の倍数でない式 2n+1 は
2(3n+0) + 1 = 6n + 1 (3の倍数でない)
2(3n+1) + 1 = 6n + 3 (3の倍数)
2(3n+2) + 1 = 6n + 5 (3の倍数でない)
[n=0,1,2,3, ...]
と書ける
従って 3 の次に来る素数は 3の倍数でない式
6n+1, 6n+5
の2つ式で 3より大きい数の中で最小の数 である
ここで n=0 において 3より大きい数の中で最小の数 である 5 が見つかり 5 は素数である
ここで 3の倍数でない式 6n+1 と 6n+5 は
6(5n+0) + 1 = 30n + 1 (5の倍数でない)
6(5n+1) + 1 = 30n + 7 (5の倍数でない)
6(5n+2) + 1 = 30n + 13 (5の倍数でない)
6(5n+3) + 1 = 30n + 19 (5の倍数でない)
6(5n+4) + 1 = 30n + 25 (5の倍数)
6(5n+0) + 5 = 30n + 5 (5の倍数)
6(5n+1) + 5 = 30n + 11 (5の倍数でない)
6(5n+2) + 5 = 30n + 17 (5の倍数でない)
6(5n+3) + 5 = 30n + 23 (5の倍数でない)
6(5n+4) + 5 = 30n + 29 (5の倍数でない)
[n=0,1,2,3, ...]
と書ける
従って 5 の次に来る素数は 5の倍数でない式
30n+1, 30n+7, 30n+13, 30n+19, 30n+11, 30n+17, 30n+23, 30+29
の8つの式で 5より大きい数の中で最小の数 である
ここで n=0 において 5より大きい数の中で最小の数 である 7 が見つかり 7 は素数である
ここで先ほどと同様に 5の倍数でない式を
30n(7n+0) + 1 = 210n + 1 (7の倍数でない)
30n(7n+1) + 1 = 210n + 31 (7の倍数でない)
30n(7n+2) + 1 = 210n + 61 (7の倍数でない)
30n(7n+3) + 1 = 210n + 91 (7の倍数)
30n(7n+4) + 1 = 210n + 121 (7の倍数でない)
30n(7n+5) + 1 = 210n + 151 (7の倍数でない)
30n(7n+6) + 1 = 210n + 181 (7の倍数でない)
30n(7n+0) + 7 = 210n + 7 (7の倍数)
30n(7n+1) + 7 = 210n + 37 (7の倍数でない)
30n(7n+2) + 7 = 210n + 67 (7の倍数でない)
30n(7n+3) + 7 = 210n + 97 (7の倍数でない)
(中略)
30n(7n+5) + 29 = 210n + 179 (7の倍数でない)
30n(7n+6) + 29 = 210n + 209 (7の倍数でない)
[n=0,1,2,3, ...]
と書ける
従って 7 の次に来る素数は 7の倍数でない式 で 7より大きい数の中で最小の数 である
同様の繰り返しで素数を探索できる
●備考
- このアルゴリズムの問題点は式の保持にメモリが大量に必要になることである
- 素数探索の式 kn+d はそれまでの素数の倍数を含まない数を導き出す式であり
素数探索の式 kn+d において素数であることが保障されるのは最後に見つかった素数より大きい数で最小の数のみである
- 素数探索の式 kn+d において n=0 のときの値、すなわち d が一見すると素数のように見えるが
今後見つかる素数の倍数である可能性があるためそれらが素数であるかどうかは分からない
※俺は数学に明るくないのでこの部分が正しいかどうかは分からない分からない
最終更新：2014年04月15日 06:35
