第２２講　素数探索を題材としたマルチスレッドプログラミングの学習
第２話 素数探索プログラミングのヒント

マルチスレッド対応プログラムによって、CPU使用率が１００％になっている状態を最初に見て頂きましょう。

これをご覧になった読者の皆さんは、すぐにもマルチスレッドの方法を知りたいでしょうが、
少々お待ちください。
マルチスレッド対応プログラムの題材の方を先に示さなければならないからです。
今回の題材は、講の表題にあるように素数の探索です。
最初に、素数の探索をシングルスレッドでプログラミングしてから、
それをマルチ化します。

さて、素数と何でしたか。
２，３，５，７，１１，１３，１７，・・・
といった数が素数ですね。
素数とは、１か自分自身でしか割りきれない数を言います。

素数であるかどうかを調べるにはどうしたらよいでしょうか。
例えば、１５１は素数でしょうか。
これを判定するには、
ルート１５１（つまり１５１の正の平方根）以下の素数で１５１を割っていって、
割り切れるものがあるかを調べれば分かります。
理由は、ルート１５１より大きい整数では１５１は割り切れません。
例えば、１６の約数を考えると１６を除けば１，２，４というようにすべてルート１６以下です。
一般的にａの約数はａを除けばルートａ以下なのです。
ルート１５１以下の素数だけで言い理由は、素数以外は必ず素因数分解できて、
素数の積で表せるので、もしルート１５１以下の整数で割りきれるとすれば、
必ずルート１５１以下の素数で割りきれます。
ルート１５１以下のすべての素数で割りきれれば１５１は素数でなく、
割り切れなければ素数です。

ルート１５１は、およそ１２．３ですから、１２以下の素数、すなわち２，３，５，７，１１で割って、
割り切れれば素数でなく、割り切れなければ素数です。
１５１は奇数ですから、明らかに２では割り切れません。
２以外の素数はすべて奇数です。
偶数なら２で割り切れてしまうからです。
また、各位の数字の和は１＋５＋１＝７ですから、３でも割り切れません。
１のくらいの数字は、１ですから５の倍数でもありません。
１５１÷７＝２１・・・４で７でも割り切れません。
１５１÷１１＝１３・・・８で１１の倍数でもありません。
結局、１２以下のどの素数で割っても割りきれませんから、１５１は素数です。

したがって、配列ａ[N]（Nは探索する範囲の上限）を用意して、
発見した素数をａ[０]＝２，ａ[１]＝３，ａ［２］＝５，ａ［３］＝７，・・・などと素数を蓄えていって、
該当の整数を蓄えた素数で割りきれるかどうかを調べればよいことになります。
ａ[０]＝２だけは偶数なので、
これは手動で入れて、
３以上の奇数について、for文で素数であるか判定していけばよいことになります。
const int N=1000000000;
int i;
a[0]=2;
for(i=3;i<N;i+=2){
　　　　　・
　　　　　・
　　　　　・


それから、素数を蓄えていって割る方法以外に
整数の平方根以下の奇数で割っていって、
割り切れるかどうかを調べる方法もあります。

皆さん、２つのプログラミングをしてどちらが速いか、調べてみてください。
一見すると素数を蓄えていって割る方法の方が速そうですが、
実際にはどうでしょうか。

シングルで速い方を採用し、それをマルチスレッド化します。

では皆さん、ビルドして実行すると下のようになるようにプログラミングしてみてください。

尚、データグリッドビューについては第１５講 関数の再帰的呼び出し☆☆
の第８話 DataGridViewによる順列作成ソフトの改良その１から第10話 DataGridViewによる順列作成ソフトの改良その３
までを参照してください。参照された場合には、ブラウザの戻るで戻ってください。

第２２講第１話へ 第２２講第３話へ



VC++講義第１部へ
vb講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座