1〜100までの自然数の集合を、Range[100]と表しておく。i、jを 1≦i、j≦s (ただし、sは
33以上の適当な整数）で、i+j+2ij なる計算で決まる数を寄せ集めた集合をSとする。
次に、Range[100]からSの要素を抜き取り、できた集合をR'とする。（エラトステネスの篩
とは異なる抜き取りになる。）
R'の各要素rに対し、2r+1を作り出すと例外なく、すべて素数が作られる。
（3,5,7,･･･,199の45個の素数ができる。)
同じく、Range[1000]からは、i、jを1≦i、j≦s （ただし、sは330以上の適当な整数）で同じ
作業をやると、3,5,7,･･･,1999の302個の素数ができる。
Range[10000]からは、i、jを1≦i、j≦s （ただし、sは3330以上の適当な整数）で、
3,5,7,･･･,19997の2261個の素数ができる。
Rangeの大きさとsの範囲の取り方に関係はありそうなんですが、Rangeが大きければ大き
いほどエラトステネスの篩にくらべ、効率がいいように思われます。
何方かこのやり方に詳しい方はプログラムを組んだ場合に、1,000,000個の素数を発見す
るまでにかかる時間の比較をして頂けませんか？
また、これをもっと効率よく運用する方法(i、jを同じ範囲で動かすので重複する数が産み
出される無駄ができる。）がありましたら教えて下さい。
らすかるさんからのコメントです。（平成２７年１０月６日付け）
エラトステネスの篩にくらべ、本当に効率がいいでしょうか？
例えば、2000万までの奇素数1270606個を得るのに、Range[1000万]で、s≧3333330とす
るわけですよね。
そうすると、i、jのペアは（i≦jとして）3333330H2=5555546111115組あるわけですから、Sを
作るだけで、5555546111115回の計算が必要です。
エラトステネスの篩ならば、
2000万以下の3より大きい3の奇倍数3333332個を消去
2000万以下の5より大きい5の奇倍数1999999個を消去
2000万以下の7より大きい7の奇倍数1428570個を消去
2000万以下の11より大きい11の奇倍数909090個を消去
・・・
2000万以下の4463より大きい4463の奇倍数2240個を消去
合計消去回数 18920365回で終わりますから、処理ループ回数だけ考えてもエラトステネス
の篩の方がはるかに効率が良いと思います。
また、100万個では少なすぎではないでしょうか。エラトステネスの篩では一瞬で終わって
しまいます。
さらに、少なくともiを1からsまで変化させ、jをiからsまで変化させれば、1≦i≦j≦sとなり、単
純な重複は削除できますね。
DD++さんからのコメントです。（平成２７年１０月６日付け）
i+j+2ij って変形すると、{(2i+1)(2j+1)-1}/2 ですから、単に「奇数を全パターン掛け合わせれ
ば合成数が全部出るから、残りが素数だね」と計算量が変わらないような。数が大きくなれば
なるほどエラトステネスの篩に比べて効率が悪いと思います。
ユークリッド方式素数の構成 ＧＡＩ １００６
自然数で素数を作る。
1+1 ○
1*2+1 ○
1*2*3+1 ○
1*2*3*4+1 ×
1*2*3*4*5+1 ×
･････････
1*2*3*････*11+1 ○
･････････
1*2*3*･･････*27+1 ○
････････････････
こうして、{1,2,3,11,27,37,41,73,77,116,154,･･････} なるものが集まる。→ 参考：「A002981」
1+1 ○
1*2+1 ○
1*2*3+1 ○
1*2*3*4+1 ×
1*2*3*5+1 ○
1*2*3*5*6+1 ○
1*2*3*5*6*7+1 ×
1*2*3*5*6*8+1 ×
1*2*3*5*6*9+1 ○
1*2*3*5*6*9*10+1 ×
1*2*3*5*6*9*11+1 ×
1*2*3*5*6*9*12+1 ○
1*2*3*5*6*9*12*13+1 ×
1*2*3*5*6*9*12*14+1 ×
1*2*3*5*6*9*12*15+1 ×
1*2*3*5*6*9*12*16+1 ○
･････････････････
こうして、{1,2,3,5,6,9,12,16,22,25,29,31,35,47,57,61,66,79,81,････}なるものが集まる。
（→ 参考：「A046966」）
素数で素数を作る。
2+1 ○
2*3+1 ○
2*3*5+1 ○
2*3*5*7+1 ○
2*3*5*7*11+1 ○
2*3*5*7*11*13+1 ×
2*3*5*7*11*13*17+1 ×
2*3*5*7*11*13*17*19+1 ×
･････････････････････
2*3*5*7*11*13*17*19*23*29*31+1 ○
･････････････････････
こうして、{2,3,5,7,11,31,379,1019,1021,2657,3229,4547,4787,････}なるものが集まる。
（→ 参考：「A005234」）
2+1 ○
2*3+1 ○
2*3*5+1 ○
2*3*5*7+1 ○
2*3*5*7*11+1 ○
2*3*5*7*11*13+1 ×
2*3*5*7*11*17+1 ×
2*3*5*7*11*19+1 ○
2*3*5*7*11*19*23+1 ×
2*3*5*7*11*19*29+1 ○
2*3*5*7*11*19*29*31+1 ×
2*3*5*7*11*19*29*37+1 ○
･････････････････････････
こうして、{2,3,5,7,11,19,29,37,47,67,103,179,191,223,271,････}なるものが集まる。
（→ 参考：「A039726」）
