素数の計算

素数の計算をするプログラムを40行ほど書いて走らせてみました。
走らせる前から32ビットで表せる限界で止まると分かっています。
それでも、そこまでに幾つの素数があるか調べてみよう。
そう思ってプログラムを走らせた途端に色々の問題が出て来ました。
素数は秒間100個以上発見されてディスプレイに読み切れないほど、
どんどん流れて行ってしまいます。
素数は珍しい数でも何でもなく、
千万単位の数の中におよそ2%ほど含まれていて、
それがどんどん画面を流れて行く。
素数を導きだす方程式は存在しないのですが、
プログラムなら10行ほどで素数かどうか判定できます。
いま組み立てたプログラムが現代の方程式なんだと考えを改めました。
プログラムの実行は、ひと晩で終わります。
2コアのノートパソコンが熱くなって、それで8時間の計算。
昨晩思い立ってから、いま3度目の計算を始めた所です。
少し古いパソコンでも待ち時間をかけてやれば良いので、
使わなくなったパソコンを出して来てそれで計算しようと考えました。
はじめは秒間100個の素数を見つけ出すプログラムでも、
計算の桁が大きくなってくると、計算時間は増えて行きます。
32ビットの上限近くだと秒間で10個の素数を計算するでしょう。
テレビばかり見ているより、プログラムが楽しい時もあります。
それは昨晩のひとときの出来事で、
また計算を自動にして、
テレビの音を聞きながら、
数が流れるのを眺めています。

// 素数計算32.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//

#include "stdafx.h"

// デバッグ用中間印字あり
#define DEBUG_PRINT 1

// 素数かどうかの判定
int is_prime(unsigned int i)
{
    for(unsigned int div=2;i>(div*2);div++) {
        // 割り切れると素数でない
        unsigned int ans = i / div;
        if(i == (ans * div)) {
            return 0;
        }
    }
    // 割り切れる数がなかったので素数である
    return 1;
}

// メイン関数
int _tmain(int argc, _TCHAR* argv[])
{
    unsigned int i=0;
    unsigned int prime_count=0;
    for(i=1;i<0xffffffff;i++){
        if(is_prime(i) == 1) {
#ifdef DEBUG_PRINT
            printf("%d ",i);
#endif
            prime_count++;
        }
    }
    printf("%d/%d",prime_count,i);
    while(1){
        ;// DOSプロンプトが消えないようループ
    }
    return 0;
}

広告を非表示にする