第18講 マルチスレッドプログラミング=並列処理プログラミング

第6話 7スレッド素数探索プログラム解説

プログラムスレッド上で展開される関数部分の再掲
void f1(void *a){//7で割ると1余る素数の探索
   cn1=0;
   for(int i=1;i<1001;i+=7){
    if(sh(i)){
       s1[cn1]=i;
       cn1++;
    }
   }
   t1=0;
}
void f2(void *a){//7で割ると2余る素数の探索
   cn2=0;
   for(int i=2;i<1001;i+=7){
    if(sh(i)){
       s2[cn2]=i;
       cn2++;
    }
   }
   t2=0;
}
void f3(void *a){//7で割ると3余る素数の探索
   cn3=0;
   for(int i=3;i<1001;i+=7){
    if(sh(i)){
       s3[cn3]=i;
       cn3++;
    }
   }
   t3=0;
}
void f4(void *a){//7で割ると4余る素数の探索
   cn4=0;
   for(int i=4;i<1001;i+=7){
    if(sh(i)){
       s4[cn4]=i;
       cn4++;
    }
   }
   t4=0;
}
void f5(void *a){//7で割ると5余る素数の探索
   cn5=0;
   for(int i=5;i<1001;i+=7){
    if(sh(i)){
       s5[cn5]=i;
       cn5++;
    }
   }
   t5=0;
}
void f6(void *a){//7で割ると6余る素数の探索
   cn6=0;
   for(int i=6;i<1001;i+=7){
    if(sh(i)){
       s6[cn6]=i;
       cn6++;
    }
   }
   t6=0;
}
char sh(int g){
   if(g==1)return(0);
   if(g==2)return(1);
   if(g==3)return(1);
   if(g>0 && g%2==0)return(0);
   for(int i=3;i<=sqrt((double)g);i+=2)if(g%i==0)return(0);
   return(1);
}


解説
各スレッドから書き込むと、
スレッドは並列に働いていますので、
いろいろなタイプ(分類)がごちゃ混ぜに書き込まれてしまいますので、
コンソールへの書き込みはすべてルートスレッドにしてあります。
   cout<<"7で割ると1余る素数"<<endl;
   for(i=0;i<cn1;i++){
     cout<<s1[i]<<" ";
     if(i>0 && i%10==0)cout<<endl;
   }
   cout<<endl;
     ・・・・・・・
     ・・・・・・・
     ・・・・・・・

さて、
void f1(void *a){//7で割ると1余る素数の探索
   cn1=0;
   for(int i=1;i<1001;i+=7){
    if(sh(i)){
       s1[cn1]=i;
       cn1++;
    }
   }
   t1=0;
}
について解説しましょう。
7で割って1余る整数は、
1,8,15,22,29,・・・・
です。
1から始めて7ずつ加えていけば良いのです。
7ずつ加えていくので、i+=7というわけです。
でも、これで7以外の素数が漏れなく網羅されるのでしょうか。
j
を小さい順に並べていけば、
2,3,5,11,13,19,23,29,31,37,41,47,・・・
と確かに漏れがなく素数が列挙されていることが分かります。

すべて検討されている理由は、
(7で割ると1余るグループ)1,8,15,22,29,・・・・
(7で割ると2余るグループ)2,9,16,23,31,・・・・
(7で割ると3余るグループ)3,10,17,24,32,・・・・
(7で割ると4余るグループ)4,11,18,25,33,・・・・
(7で割ると5余るグループ)5,12,19,26,34,・・・・
(7で割ると6余るグループ)6,13,20,27,35,・・・・
を小さい順に並べ直せば、
1,2,3,4,5,6,8,9,10,11,12,13,15,16,17,18,19,
20,22,23,24,・・・
と7の倍数を除く整数がすべて入っているからです。
7の倍数は、7以外は素数ではありませんから、
7の倍数ははじめから入れる必要がないのです。

ところで、
(7で割ると1余るグループ)1,8,15,22,29,・・・・
(7で割ると2余るグループ)2,9,16,23,31,・・・・
(7で割ると3余るグループ)3,10,17,24,32,・・・・
(7で割ると4余るグループ)4,11,18,25,33,・・・・
(7で割ると5余るグループ)5,12,19,26,34,・・・・
(7で割ると6余るグループ)6,13,20,27,35,・・・・
をみると、無駄なものが検討されていることが分かります。
2以外の偶数はすべて素数でないのですから、
偶数は検討対象から外すべきです。
というわけで、コードは改良の余地があります。
皆さん改良して下さい。


第5話へ 第7話へ

a

eclipse c++ 入門講義第1部へ

魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義(基礎から応用まで)
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第1部
eclipse java 入門
java 入門 サイト 基礎から応用まで
VC++ C言語 C++ 入門 初心者 基礎から応用まで
本サイトトップへ