素数の候補は、6n±1でかけます。これは、単に２と３の倍数を除いた整数表現です。これでみると、
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |||||||||||||||||||||||||||||
| 5 | 7 | 11 | 13 | 17 | 19 | 23 | 25(5×5) | 29 | 31 | |||||||||||||||||||||||||||||
| 35(5×7)(7×5) | 37 | 41 | 43 | 47 | 49(7×7) | 53 | 55(5×11) | 59 | 61 | |||||||||||||||||||||||||||||
| 65(5×13) | 67 | 71 | 73 | 77(7×11) | 79 | 83 | 85(5×17) | 89 | 91(7×13) | |||||||||||||||||||||||||||||
| 95(5×19) | 97 | 101 | 103 | 107 | 109 | 113 | 115(5×23) | 119(7×19) | 121 | |||||||||||||||||||||||||||||
| 125(5×25) | 127 | 131 | 133 | 137 | 139 | 143 | 145(5×29) | 149 | 151| 155(5×31) | 157 | 161(7×23) | 163 | 167 | 169 | 173 | 175(5×35)(7×25) | 179 | 181 | |
この表は、途中ですが、一般に素数候補Ｋは、Ｋが素数候補の積であるとき、
K=（6m±1)×(6n±1)
とかくことができます。
しかし、K=6k±1ですから、
6k±1=（6m±1)×(6n±1)
6k-1=（6m±1)×(6n±1)より、
6k-1=（6m+1)×(6n-1) ----(1)
6k-1=（6m-1)×(6n+1) ----(2)
6k+1=（6m±1)×(6n±1)より、
6k+1=（6m+1)×(6n+1) ----(3)
6k+1=（6m-1)×(6n-1) ----(4)
の4とおりしかありません。
これ以外であれば、間違いなくそれは、素数になります。
これは、新種のエラトステネスの篩になります。
では、篩をどうやれば、効率的に行うことができるでしょうか。
5×5,5×7,5×11,5×13,5×17,5×19,5×23,5×25,......
7×5,7×7,7×11,7×13,7×17,7×19,7×23,7×25,......
11×5,11×7,11×11,11×13,11×17,11×19,11×23,11×25,......
13×5,13×7,13×11,13×13,13×17,13×19,13×23,13×25,......
17×5,17×7,17×11,17×13,17×17,17×19,17×23,17×25,......
一般に、ある数6n-1は、5よりはじめて、n×2-1番目であり、ある数6n+1は、5よりはじめて、n×2番目である。
5×5=25は、6×4+1より、表の先頭から8番目,5×7=35は6×6-1より11番目である。したがって、５よりはじめて７番め、そこから3番目そこから7番目そこから3番目の繰り返しでぬけてゆく。
7×5=35は、6×6-1より、表の先頭から11番目,7×7=49は6×8+1より16番目である。 7×11=77は、6×13-1より、表の先頭から25番目, 7×13=91は、6×15+1より、表の先頭から30番目である。したがって、５よりはじめて11番め、そこから5番目そこから9番目そこから5番目の繰り返しでぬけてゆく。
11×5=55は、6×9+1より、表の先頭から18番目,11×7=77は6×13-1より25番目である。 11×11=121は、6×20+1より、表の先頭から40番目, 11×13=143、6×24-1より、表の先頭から47番目である。したがって、５よりはじめて18番め、そこから7番目そこから15番目そこから7番目の繰り返しでぬけてゆく。
エラトステネス篩法によるsosuu-1.tgz のダウンロード 2011.4.10更新
sosuu-1.tgzの中身の説明
漢字コードの違いにより
sosuu-1.sjis.c シフトJISコード
sosuu-1.euc.c EUCコード
sosuu-1.utf.c UTF8コード
３つのCのソースプログラムが入っています｡
処理系の漢字環境で選択して下さい｡
ソースのはじめの行の以下の行を変えることで求める素数候補を指定できます｡
#define nn 50000002
今5億2となっていますが、これを書き換えることで素数候補の数を変えることができます｡
1億はメモリ400MB消費しますので5億では2GB以上必要です｡
足りないとスワップが起きてとんでもない時間がかかります｡
なお、gccのバージョンは4.1.2で環境はVine Linux5CRで確認しています｡
このプログラムは、64MBのメモリのLINUXで270万個の素数を表による虱潰し法の5分にたいして12秒で、求めます。