実行画面
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
〜
199211 199247 199261 199267 199289 199313 199321 199337 199343 199357
199373 199379 199399 199403 199411 199417 199429 199447 199453 199457
199483 199487 199489 199499 199501 199523 199559 199567 199583 199601
199603 199621 199637 199657 199669 199673 199679 199687 199697 199721
199729 199739 199741 199751 199753 199777 199783 199799 199807 199811
199813 199819 199831 199853 199873 199877 199889 199909 199921 199931
199933 199961 199967 199999
素数が1から200000の間に17984個ありました。
素数探索にかかった時間は1.234000秒です。
プロジェクト終了
を実現するプログラム例
#include<stdio.h>
#include<time.h>
char f(int a);
int main(){
int i,cn;
clock_t hj,ow;
hj=clock();
cn=0;
for(i=1;i<200001;i++){
if(f(i)){
printf("%d ",i);
cn++;
if(cn%10==0)printf("\n");
}
}
printf("\n");
printf("素数が1から200000の間に%d個ありました。\n",cn);
ow=clock();
printf("素数探索にかかった時間は%f秒です。\n",(double)(ow - hj) / CLOCKS_PER_SEC);
printf("プロジェクト終了\n");
return(0);
}
char f(int a){
int w,i;
w=a/2;
if(a==1)return(0);
if(a==2)return(1);
if(a%2==0)return(0);
for(i=3;i<=w;i+=2){
if(a%i==0)return(0);
}
return(1);
}
素数探索プログラムVer.2
まだ、改善の余地が２つあります。
５９が素数であるかどうか判定するのに、
約半分まで割っていきましたが、
実はそんなに割る必要はありません。
それを理解して頂くために、
例えば、１６の約数を考えて下さい。
１，２，４，８，１６
（１，１６）、（２，８）は相棒でした。
一方で割ると、他方は一方で割ったときの商でした。
ですから、
約数の個数を数えるとき、１と２の２個を２倍して
それに４も数えて、１を加えれば約数の個数が求まります。
約数の個数を数えるには、
半分ではなく、４まで割っていけば良いのです。
１６に対して４とはどういう数でしょうか。
中学３年生以上の方はお分かりですよね。
小学生でもきっと気がついている人もいるはずです。
１６＝４×４
です。
同じ数をかけることを２乗するといいます。
この言葉を使えば、４の２乗が１６です。
この４のことを１６の平方根といいます。
２乗するとaになる数をaの平方根といい、
と表し、ルートaと読みます。int w,a;
２つの整数型の変数を用意して、
w=sqrt(a);
とすれば、aの平方根がwに収納されます。
正確にいうと小数部分は切り捨てられて、
整数に丸められていますが、
素数を探索するときには、
この丸められたwまで割っていけば良いのです。
ですから、５９であれば
７×７＝４９、８×８＝６４
ですから、７まで割っていけば良いのです。
w=sqrt(59);
でwは７になりますから、これでよいのです。
１を除いて、２、３，５，７で割り切れなければ、
素数であることが確定します。
更に改善したプログラムの実行結果
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
〜
199211 199247 199261 199267 199289 199313 199321 199337 199343 199357
199373 199379 199399 199403 199411 199417 199429 199447 199453 199457
199483 199487 199489 199499 199501 199523 199559 199567 199583 199601
199603 199621 199637 199657 199669 199673 199679 199687 199697 199721
199729 199739 199741 199751 199753 199777 199783 199799 199807 199811
199813 199819 199831 199853 199873 199877 199889 199909 199921 199931
199933 199961 199967 199999
素数が1から200000の間に17984個ありました。
素数探索にかかった時間は0.031000秒です。
プロジェクト終了
３つに時間を書いておくと、
2.388000秒→1.234000秒→0.031000秒
ですから、大跳躍の一途です。
最初に比較して約77倍になりました。
ちょっと工夫するだけで、
大改善できる・・・これがプログラミングのおもしろさです。
