プログラムの威力を息子に示す！？
ちょうど息子が算数で公倍数の問題を解いていたときに、「公倍数って素数を知っていると便利だよね」という話になり、素数の説明をした後に、「1から100までの間で素数を全部求めよう」ということになり、こんな時こそプログラムのパワーを見せてあげようと、MacBookAirを持ってきて、C言語でささっとプログラムを作って動かしてみせました。
#include <stdio.h>
int main(int argc,char *argv[])
{
int i,j,bad;
int end=atoi(argv[1]);
for(i=1;i<=end;i++){
bad=0;
for(j=2;j<i;j++){
if(i%j==0){
bad=1;
break;
}
}
if(bad==0){
printf("%d\n",i);
}
}
return(0);
}
実に簡単なプログラムですが、これなら1000まででも、10000まででも・・・と試していたら、100万にもなると結構時間がかかります。。
real 6m20.631s
user 5m46.385s
sys 0m1.532s
「こりゃ、いかん！高速化だ」と、ちょっとだけ変えました。
#include <stdio.h>
int main(int argc,char *argv[])
{
int i,j,bad,mid;
int end=atoi(argv[1]);
for(i=1;i<=end;i++){
bad=0;
mid=i/2+1;
for(j=2;j<=mid;j++){
if(i%j==0){
bad=1;
break;
}
}
if(bad==0){
printf("%d\n",i);
}
}
return(0);
}
単に判定する数の半分までしか見ないようにしただけですが、
real 3m23.727s
user 3m5.853s
sys 0m0.857s
半分くらいで終わるようになります。
しかし、これでもまだ遅いので、「エラトステネスのふるい」を使ってみました。すでに見つけた素数だけでチェックする方法ですね。
#include <stdio.h>
int Sosu[1000000];
int SosuNo=0;
int main(int argc,char *argv[])
{
int i,j,bad;
int end=atoi(argv[1]);
for(i=1;i<=end;i++){
bad=0;
for(j=0;j<SosuNo;j++){
if(i%Sosu[j]==0){
bad=1;
break;
}
}
if(bad==0){
printf("%d\n",i);
if(i!=1){
Sosu[SosuNo]=i;
SosuNo++;
}
}
}
return(0);
}
100万までだと、素数は78498個とわかっているので、素数を格納する配列は固定で確保して手抜きをしています。
real 0m31.196s
user 0m29.006s
sys 0m0.133s
断然高速です！
どうせならと、こちらもチェックする数の半分までを対象にすると、
#include <stdio.h>
int Sosu[1000000];
int SosuNo=0;
int main(int argc,char *argv[])
{
int i,j,bad,mid;
int end=atoi(argv[1]);
for(i=1;i<=end;i++){
bad=0;
mid=i/2+1;
for(j=0;j<SosuNo;j++){
if(Sosu[j]>mid){
break;
}
if(i%Sosu[j]==0){
bad=1;
break;
}
}
if(bad==0){
printf("%d\n",i);
if(i!=1){
Sosu[SosuNo]=i;
SosuNo++;
}
}
}
return(0);
}
ちょっとソースは長くなりますが、
real 0m16.461s
user 0m15.692s
sys 0m0.059s
さらに高速に！
まあ、高速化はともかく、人間がやると大変なことを、いとも簡単にコンピューターに計算させるすばらしさを息子に見せてみたのですが・・・すばらしさがわかったかどうか。。
アルゴリズムの高速化は、「エラトステネスのふるい」のように、公理を使うのがもちろん常識ですが、実は「半分までしか見ない」というような、ちょっとした手抜きをするのもポイントです。
一つ気になるのが・・・MacOSXだったので、ターミナルを出して、エディタでソースを書いて、gccでコンパイルして、実行、とできたのですが（開発環境はOSのCDに入っています）、Windowsだとそう簡単ではないですよねぇ。まあ、Visual Studioも今ではフリー版があるので、それをインストールして使う感じですかねぇ。。Eclipse
でJavaとかもありですが・・・