オルタナティブ・ブログ > プログラマー社長のブログ >

プログラミングでメシが食えるか!?

プログラムの威力を息子に示す!?

»

ちょうど息子が算数で公倍数の問題を解いていたときに、「公倍数って素数を知っていると便利だよね」という話になり、素数の説明をした後に、「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とかもありですが・・・

Comment(9)