第７話 前判定と後判定の違い
コード再掲
#include<iostream>
#include<math.h>
using namespace std;
using namespace System;
int cn;
void f(int a);
char h(int a);
int main(){
int n;
DateTime^ hj=DateTime::Now;
cout<<"素数の探索範囲をキーボードから入力してください。"<<endl<<"ｎ＝";
scanf("%d",&n);
cn=1;
f(n);
DateTime^ ow=DateTime::Now;
TimeSpan sa=ow->Subtract(*hj);
cout<<"１から"<<n<<"までの素数の総数は"<<cn<<"です。"<<endl;
cout<<"計算時間は"<<sa.TotalSeconds<<"秒です。"<<endl;
}
void f(int a){
int i=3;
cout<<"2"<<" ";
do{
if(h(i)){
cout<<i<<" ";
cn++;
}
i+=2;
}while(i<=a);
cout<<endl;
}
char h(int a){
int i=3;
do{
if(a%i==0)return(0);
i+=2;
}while(i<=(int)sqrt((double)a));
return(1);
}
原因はピンクにあります。
while文
while(i<=(int)sqrt((double)a));{
if(a%i==0)return(0);
i+=2;
}
との違いは何でしょうか。
h(3)によって素数判定関数hが呼び出せれ、
３が素数であるか判定しようとします。
(int)sqrt((double)a)=(int)(1.732)=1
ですから、前判定の場合
i<=(int)sqrt((double)a)
は偽ですから、while文は実行されません。
実行されないので、return(1);によって1を返します。
つまり、素数であるの判定になりました。
しかし、do...while文の場合判定は後で行われるので、
do{
if(a%i==0)return(0);
i+=2;
}while(i<=(int)sqrt((double)a));
は1回は実行されてしまうのです。
すると3は3で割ったとき余りが0ですから、
return(0);が実行されて0が返されてしまいます。
すなわち、素数でないと判定となってしまうのです。
では、do...while文版をどのように改良した正確にカウントされるようになるでしょうか。
第６話へ 第８話へ
