二パターンの素数の判定・列挙

こんにちは！マツケンです！

プログラミングにおいて、「プロジェクトオイラー」を中心にブログを書いていますが、興味深いことや面白いことも別枠の「プログラミング」で書き残していこうとおもいました！

今日は、おそらく大学の課題などで頻出する「素数判定・列挙を行うプログラム」について面白いことがあったので書き残していきます！

そもそも素数とは...

　素数とは
「1と自分自身以外では割り切れない2以上の自然数」
のことです。素数って無限に続き「最大の整数は何なのか」とか「素数を求める公式はない」とか高校時代に友達とよく話していたことを思い出します...（懐かしい）

大学一年生の頃の僕はひたすら数を上げつつ条件判定を行うというめっちゃ効率の悪いことをしていましたが、アルゴリズムを深く考えていくことにより、
「時間計算量の効率化、探索範囲の効率的な削減」
を行うことができます！これってとても大事なことだし、おもしろいんですよ...！

素数判定1「単純に素数判定」

　その名の通り、単純に素数判定を行っていきます。まずはプログラム↓

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#define N 10000000

int isPrime(int x){//その数が素数であるかの判定。素数なら1を素数でないなら0を返す。
    int sq_num = (int)sqrt((double)x);

    if(x == 2) return 1;//2は素数
    if(x < 2 || x % 2 == 0) return 0;//2より小さい数、2で割れるものは素数でない。
    for(int n = 3; n <= sq_num; n += 2)//探索範囲の削減
        if(x % n == 0) return 0;
    return 1;
}

int main(void){

    int *prime;//素数と分かったものを入れていく配列*/
    prime = (int *) malloc(sizeof(int) * N);
    int count = 2;//何番目の素数を探しているか
    int num = 1;//素数かどうか見ていく数
    clock_t start, end;

    start = clock();

    prime[1] = 2;

    while(num < N){
        num += 2;
        if(N < num) break;
        if(isPrime(num)==1){
            prime[count] = num;
            count ++;
        }
    }

    end = clock();//列挙を含めなかった際の測定時間の終わり

    for(int i = 1; i < count; i++){
        printf("%d番目の素数は%dです。\n", i, prime[i]);
    }
    //end = clock();//列挙まで含めた際の測定時間の終わり
    printf("かかった時間%d[ms]\n", end - start);

    free(prime);
    return 0;
}

注釈を所々に挟んでいますので、概略のみまとめると、
「素数と分かった数をその都度配列primeに格納していく。関数isPrimeでは素数判定を行い、素数ならば１を、そうでないなら０を返す。探索範囲は判定する数の√以下を探索すればよい。」
です。最後の探索範囲について少し証明を書くと

Nを素数でないものとする。すると、Nは単純な二つの自然数a,b(1< a < b)を用いて
N = a * b
と書けるとする。N = a * b ≧ a^2となり、√N ≧ a　となる。Nを素数かどうか判定するとき、aの値が見つからなければNは素数、見つかればNは素数でないことが判定できる。

だからです！

素数判定2「エラトステネスの篩」

　単純に探索していくのではなく「探索する範囲を全て素数の候補とする」ことがポイントです！素数を小さい数から探していくのですが、ある数が素数であるとき、その倍数を素数の候補から除外していく処理を繰り返すにつれて、残った数が素数となるんです！
初めてこのアルゴリズムでプログラムを組んだ時は遅そうだな～と思っていたのですが、ちょっと面白いことが判明したのです！
プログラム(´∀｀)

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#define N 10000000

int main(void){
    
    int sq_num = (int)sqrt((double)N);
    int count = 1;
    int *prime;//素数であるものに1を、そうでないものに0を対応させる配列。
    prime = (int *) malloc(sizeof(int) * N);
    clock_t start, end;

    start = clock();

    for (int i = 0; i < N; i++)
        prime[i] = 1;  //素数の候補を作るために、全ての数に1を入れる。
    prime[0] = 0;//0は素数ではない。    
    prime[1] = 0;//1は素数じゃない。

    for (int i = 2; i <= sq_num; i++) {//探索範囲の削減
        if (prime[i] == 1)          //注目している数、prime[i]が素数なら
        for (int j = i; i * j <= N; j++)//j ≧ i
            prime[i * j] = 0;  //素数の倍数は素数じゃない。
        }
    end = clock();//列挙を含めなかった際の測定時間の終わり
    
    for (int i = 1; i < N; i++)
        if (prime[i] == 1){  //1が入っているものが素数
            printf("%d番目の素数は%d\n", count, i);
            count++;
        }
    
    end = clock();//列挙まで含めた際の測定時間の終わり
    printf("かかった時間%d[ms]\n", end - start);

    free(prime);
    return (0);
}

2つのプログラムの実行結果

気づき

　単純な素数判定とエラトステネスの篩を行った結果において、「素数を判定して列挙までする」場合においては、N が小さいと差は見られなかったが、N=10000000 でエラトステネスの篩のほうが単純な素数判定よりも大きい計算時間が見られました。
また、「素数判定を行うだけ」の時間も計測したところ、エラトステネスの篩のほうが単純な素数判定よりもN=10000000 の時に大きい計算時間が見られました。
今回僕が描いた2つのプログラムにおいては、「単純に素数判定を行い出力するプログラム」では素数のみが入っている配列 prime から値をひとつずつ列挙していくことに対し、「エラトステネスの篩によるプログラム」では、列挙する際は配列 prime に入っている数字が 0 であるか 1 であるかをすべて評価し出力していくところの違いにより、このような結果になったのか。

あるNの値を境にこんなに違いが出るんですね！