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

プログラムスレッド上で展開される関数部分の再掲
void f1(void *a){//７で割ると１余る素数の探索
　　 cn1=0;
　　 for(int i=1;i<1001;i+=7){
　　　　if(sh(i)){
　　　　　　 s1[cn1]=i;
　　　　　　 cn1++;
　　　　}
　　 }
　　 t1=0;
}
void f2(void *a){//７で割ると２余る素数の探索
　　 cn2=0;
　　 for(int i=2;i<1001;i+=7){
　　　　if(sh(i)){
　　　　　　 s2[cn2]=i;
　　　　　　 cn2++;
　　　　}
　　 }
　　 t2=0;
}
void f3(void *a){//７で割ると３余る素数の探索
　　 cn3=0;
　　 for(int i=3;i<1001;i+=7){
　　　　if(sh(i)){
　　　　　　 s3[cn3]=i;
　　　　　　 cn3++;
　　　　}
　　 }
　　 t3=0;
}
void f4(void *a){//７で割ると４余る素数の探索
　　 cn4=0;
　　 for(int i=4;i<1001;i+=7){
　　　　if(sh(i)){
　　　　　　 s4[cn4]=i;
　　　　　　 cn4++;
　　　　}
　　 }
　　 t4=0;
}
void f5(void *a){//７で割ると５余る素数の探索
　　 cn5=0;
　　 for(int i=5;i<1001;i+=7){
　　　　if(sh(i)){
　　　　　　 s5[cn5]=i;
　　　　　　 cn5++;
　　　　}
　　 }
　　 t5=0;
}
void f6(void *a){//７で割ると６余る素数の探索
　　 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<<"７で割ると１余る素数"<<endl;
　　 for(i=0;i<cn1;i++){
　　　　　cout<<s1[i]<<" ";
　　　　　if(i>0 && i%10==0)cout<<endl;
　　 }
　　 cout<<endl;
　　　　　・・・・・・・
　　　　　・・・・・・・
　　　　　・・・・・・・

さて、
void f1(void *a){//７で割ると１余る素数の探索
　　 cn1=0;
　　 for(int i=1;i<1001;i+=7){
　　　　if(sh(i)){
　　　　　　 s1[cn1]=i;
　　　　　　 cn1++;
　　　　}
　　 }
　　 t1=0;
}
について解説しましょう。
７で割って１余る整数は、
１，８，１５，２２，２９，・・・・
です。
1から始めて７ずつ加えていけば良いのです。
７ずつ加えていくので、i+=7というわけです。
でも、これで７以外の素数が漏れなく網羅されるのでしょうか。

を小さい順に並べていけば、
２，３，５，１１，１３，１９，２３，２９，３１，３７，４１，４７，・・・
と確かに漏れがなく素数が列挙されていることが分かります。

すべて検討されている理由は、
（７で割ると１余るグループ）１，８，１５，２２，２９，・・・・
（７で割ると２余るグループ）２，９，１６，２３，３１，・・・・
（７で割ると３余るグループ）３，１０，１７，２４，３２，・・・・
（７で割ると４余るグループ）４，１１，１８，２５，３３，・・・・
（７で割ると５余るグループ）５，１２，１９，２６，３４，・・・・
（７で割ると６余るグループ）６，１３，２０，２７，３５，・・・・
を小さい順に並べ直せば、
１，２，３，４，５，６，８，９，１０，１１，１２，１３，１５，１６，１７，１８，１９，
２０，２２，２３，２４，・・・
と７の倍数を除く整数がすべて入っているからです。
７の倍数は、７以外は素数ではありませんから、
７の倍数ははじめから入れる必要がないのです。

ところで、
（７で割ると１余るグループ）１，８，１５，２２，２９，・・・・
（７で割ると２余るグループ）２，９，１６，２３，３１，・・・・
（７で割ると３余るグループ）３，１０，１７，２４，３２，・・・・
（７で割ると４余るグループ）４，１１，１８，２５，３３，・・・・
（７で割ると５余るグループ）５，１２，１９，２６，３４，・・・・
（７で割ると６余るグループ）６，１３，２０，２７，３５，・・・・
をみると、無駄なものが検討されていることが分かります。
２以外の偶数はすべて素数でないのですから、
偶数は検討対象から外すべきです。
というわけで、コードは改良の余地があります。
皆さん改良して下さい。