スポンサーリンク
※サイト運営にサーバーは必須です※
～このサイトもエックスサーバー
を使用しています～
目次
はじめに
素数のリストを可能な限り早く作ってくれるプログラムを作りたいと思って、最初はいくつか作って実行スピードを調べようと思った。
だが、いくつか作った結果、実行するタイミングで結構結果が変わる。
自分でもどのパターンが最速かよくわかっていない。
オーダーで2倍も違うものはないので、どれを使ってもいいと思う。
※言語はC#。作った環境はVisual Studio 2015 。コンソールアプリケーションで作っている
※追記：バグが残っている可能性がある。
1：単純なエラトステネスのふるい
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using static System.Console; using System.Diagnostics; namespace prime_list { class Program { static void Main(string[] args) { Stopwatch st = new Stopwatch(); st.Start(); int n_ini = 10000000; bool[] n_list = new bool[n_ini] ; //bool の初期はfalse for (int i=1; i < n_ini; ++i) { if(n_list[i] == false) { for(int j=2; (i + 1) * j - 1 < n_ini;++j) { n_list[(i + 1) * j - 1] = true; } WriteLine(i+1 + "\r\n"); } } st.Stop(); WriteLine(st.Elapsed); } } } |
何も考えず、愚直にエラトステネスのふるいを実装した場合。
配列をラベル付けする数字が0から始まるのに対して、配列の中の数字は1から始まっていると考えている。その食い違いに解消のためにi+1になっている所がある。
※わかりづらいかもしれないが、素数をFalse、素数以外の数字をTrueと判定している(配列の中が最初はFalseなので)。
2：√Nで、篩を止める
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using static System.Console; using System.Diagnostics; namespace prime_list { class Program { static void Main(string[] args) { Stopwatch st = new Stopwatch(); st.Start(); int n_ini = 1000000; bool[] n_list = new bool[n_ini] ; //bool の初期はfalse int i = 1; for (i=1; (i+1)*(i+1) <= n_ini; ++i) { if(n_list[i] == false) { for(int j=2; (i + 1) * j - 1 < n_ini;++j) { n_list[(i + 1) * j - 1] = true; } WriteLine(i+1 + "\r\n"); } } for (int k = i; k < n_ini; ++k) { if (n_list[k] == false) { WriteLine(k+1 + "\r\n"); } } st.Stop(); WriteLine(st.Elapsed); } } } |
素数リストを作るときに、考えている最大の数をNとするとその平方根までの数で篩をかければ十分である。ループ文で毎回(i+1)*(i+1)で判定しているのが遅さの原因のような気がしてきたので、次のコードでは、そこも含めて改善
3:奇数の場合で考える（読み取りのみ）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using static System.Console; using System.Diagnostics; using static System.Math; namespace prime_list { class Program { static void Main(string[] args) { Stopwatch st = new Stopwatch(); st.Start(); int n_ini = 1000000; int n_root = (int)Sqrt(n_ini); bool[] n_list = new bool[n_ini] ; //bool の初期はfalse int i = 1; for (i=1; (i+1)<= n_root; ++i) { if(n_list[i] == false) { for (int j = 2; (i + 1) * j - 1 < n_ini; ++j) { n_list[(i + 1) * j - 1] = true; } //WriteLine(i+1 + "\r\n"); } } /* for(int num= (i + 1) * 2 - 1; num < n_ini; num+=i+1) { n_list[num] = true; } */ WriteLine(2 + "\r\n"); for (int k = 2; k < n_ini; k+=2) { if (n_list[k] == false) { WriteLine(k+1 + "\r\n"); } } st.Stop(); WriteLine(st.Elapsed); } } } |
篩の中のループ文の条件判定に、Sqrt()を使っている。これで少しは早くなるはず。
また、2だけ特別扱いにして結果をコンソールに出力する時に2つ飛ばしで行っている。
あと、(i + 1) * j – 1を無駄に２回計算しているのが気になってきた(forの判定とn_list[]で)。だが、色々いじくっても、逆に遅くなったので、手を加えていない。
4:奇数の場合で考える（篩+読み取り）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using static System.Console; using System.Diagnostics; using static System.Math; namespace prime_list { class Program { static void Main(string[] args) { Stopwatch st = new Stopwatch(); st.Start(); int n_ini = 10000000; int n_root = (int)Sqrt(n_ini); bool[] n_list = new bool[n_ini] ; //bool の初期はfalse WriteLine(2 + "\r\n"); for (int j = 2; 2 * j - 1 < n_ini; ++j) { n_list[2* j - 1] = true; } int i = 2; for (i=2; (i+1)<= n_root;i+=2) { if(n_list[i] == false) { for (int j = 2; (i + 1) * j - 1 < n_ini; ++j) { n_list[(i + 1) * j - 1] = true; } //WriteLine(i+1 + "\r\n"); } } for (int k = 2; k < n_ini; k+=2) { if (n_list[k] == false) { WriteLine(k+1 + "\r\n"); } } st.Stop(); WriteLine(st.Elapsed); } } } |
篩の部分でも2だけ特別扱いにしている。ぶっちゃけそんなに早くなっている感じはしなかった。
4´:奇数の場合で考える（篩+読み取り）
後でよくよく考えたら、篩の中のforのループ文（int j)の部分も2つ飛ばしで問題ない気がしてきた。ついでに、jのスタートは自分自身の数からスタートしても大丈夫だ思う。
例えば、7を素数として見つけた場合。篩をかけるのを14からスタートするのではなく、49から始めても問題ない。なぜなら、14、21、28、35、42は全て2,3,5のいずれかの倍数なので、すでに素数でないとわかっている。
また、49(7×7)の次として56（７×8）を考えるのでなく、63(7×9)を考えればいい。56は２の倍数なので素数でないとわかっている。つまり、2つ飛ばしで考え7×（奇数）を消していく。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using static System.Console; using System.Diagnostics; using static System.Math; namespace prime_list { class Program { static void Main(string[] args) { Stopwatch st = new Stopwatch(); st.Start(); int n_ini = 10000000; int n_root = (int)Sqrt(n_ini); bool[] n_list = new bool[n_ini] ; //bool の初期はfalse WriteLine(2 + "\r\n"); for (int j = 2; 2 * j - 1 < n_ini; ++j) { n_list[2* j - 1] = true; } int i = 2; for (i=2; (i+1)<= n_root;i+=2) { if(n_list[i] == false) { for (int j = (i + 1); (i + 1) * j - 1 < n_ini; j+=2) { n_list[(i + 1) * j - 1] = true; } //WriteLine(i+1 + "\r\n"); } } for (int k = 2; k < n_ini; k+=2) { if (n_list[k] == false) { WriteLine(k+1 + "\r\n"); } } st.Stop(); WriteLine(st.Elapsed); } } } |
5：6k+(1,5)で考える(読み取り）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using static System.Console; using System.Diagnostics; using static System.Math; namespace prime_list { class Program { static void Main(string[] args) { Stopwatch st = new Stopwatch(); st.Start(); int n_ini = 10000000; int n_root = (int)Sqrt(n_ini); bool[] n_list = new bool[n_ini] ; //bool の初期はfalse int i = 1; for (i=1; (i+1)<= n_root; ++i) { if(n_list[i] == false) { for(int j=2; (i + 1) * j - 1 < n_ini;++j) { n_list[(i + 1) * j - 1] = true; } //WriteLine(i+1 + "\r\n"); } } WriteLine(2 + "\r\n"); WriteLine(3 + "\r\n"); int s = 4; for (int k = 4; k < n_ini; k+=s) { if (n_list[k] == false) { WriteLine(k+1 + "\r\n"); } if (s == 2) { s = 4; } else { s = 2; } } st.Stop(); WriteLine(st.Elapsed); } } } |
読み取り時に、2と3を特別扱いする。
この場合、6ｋ+｛1,5｝を考えれば十分。
プログラム的には、数字が+2されるのと+4されるのが交互に続く。
交互に+2と+4をするための判定にif～else文を使っている分、むしろ遅くなった気がする。6ｋ+｛1、-1｝と考えても似たような問題に直面するはず。
まとめ
何度か実行した体感としては、3か4が1と比べて速くなった気がする。そんなに大きな差はないが
関連記事
この記事の経験を踏まえ、より大きな素数に対応したプログラムの紹介
～プログラミングを勉強してみませんか？～
TechAcademy [テックアカデミー] 
は無料の体験講座が用意されているので、気軽に体験できます。
※私(サイト主)も無料体験講座を実際に受けてみました(→感想)
