C言語で素数を求めるプログラム

初めに

初めまして、情報を学んでいる学生です。いきなりですが先輩が対数を求めるプログラムを作っていたので数学的なものを作ってみたく、素数を求めるプログラムを作ってみました。

単純なごり押しタイプ

#include <stdio.h>
//時間をカウントするために使う　時間測定用の部分がいらないなら削除可
#include <time.h>

int main()
{
    //時間測定用
    clock_t start, end;
    start = clock();

    //本プログラム
    int check = 1;
    while (check < 2000000)
    {
        for (int i = 2; i <= check; i++)
        {
            if (check % i == 0)
            {
                if (i == check)
                {
                    printf(" %d", check);
                }
                break;
            }
        }
        check+=2;
    }

    //時間測定用
    end = clock();
    printf("\n%.2f秒かかりました\n", (double)(end - start) / CLOCKS_PER_SEC);
}

実行時間は505.981秒でした。
単純な分序盤は早いが1000000を超えたあたりから目に見えて遅くなってしまいました。

そのため、次は素数かを確かめている部分を改善しようと思います。

素数で割り確かめる

2～checkまでを1ずつ確かめるのではなく、check以下の素数で割り余りがゼロになるかを確かめることで、後半の速度をできるだけ落とさないように作ってみました。

#include <stdio.h>
//時間をカウントするために使う　時間測定用の部分がいらないなら削除可
#include <time.h>

int main()
{
    //時間測定用
    clock_t start, end;
    start = clock();

    //本プログラム
    int check = 3;//素数かを比べる
    int primeNumber[220000];//素数格納用
    primeNumber[0]=2;//初期値
    int count=1;//素数の個数
    printf(" 2");
    while (check < 2000000)//最大数制限3000000
    {
        for(int i=0;i<count;i++)//配列を参照用
        {
            if(check%primeNumber[i]==0)//素数か確かめる
            {
                break;
            }
            else if(i==count-1)//配列の最後まで割ったか確かめる
            {
                primeNumber[count]=check;//素数を格納
                printf(" %d",check);//素数を表示
                count++;//素数の個数を増やす
            }
        }
        check+=2;

    }
    //時間測定用
    end = clock();
    printf("\n%.2f秒かかりました\n", (double)(end - start) / CLOCKS_PER_SEC);
}

実行時間は39.00秒でした。
ごり押しタイプと素数で割るのを比べると大体13倍ぐらいの差が出ました。

比較してみた

気になったので、それぞれの値でどのぐらいの実行時間がかかっているかをグラフで比べてみました。

このグラフは横軸がcheckの値(素数かを比べた値)で縦軸が値が増加するたびにどれだけ秒数がかかっているか(10000回目の実行時間 - 20000の実行時間,20000回目の実行時間 - 30000の実行時間のように)を表しています。
見てわかるように最初のプログラムのごり押しタイプがすごい勢いで増加していて、次の素数で割る方は、比較的緩やかな増加になっておりこのことから、２つ目の素数で割る方が効率的であることがわかりました。

mallocを使ったやり方(おまけ)

今回の素数で割る方は個数が少なかったからよかったもののこれ以上に出力しようとすると配列の個数が足りなくなる(配列を宣言する限界に達する)ため、mallocなどを使い限界を越えなければならないので、下記の通りに直せば動きます(コンパイラ的に1000000000あたりが限界みたいです)。

#include <stdio.h>
#include <stdlib.h>
//時間をカウントするために使う　時間測定用の部分がいらないなら削除可
#include <time.h>


int main()
{
    //時間測定用
    clock_t start, end;
    start = clock();

    //本プログラム
    int check = 3;//素数かを比べる
    int number=1000000000;
    int *primeNumber=(int *)malloc(sizeof(int)*number);//素数格納用
    if(primeNumber==NULL)
    {
        printf("失敗");
        return 0;
    }
    primeNumber[0]=2;//初期値
    int count=1;//素数の個数
    int a=0;
    printf(" 2");
    while (check < number)//最大数制限2000000
    {
        for(int i=0;i<count;i++)//配列を参照用
        {
            if(check%primeNumber[i]==0)//素数か確かめる
            {
                break;
            }
            else if(i==count-1)//配列の最後まで割ったか確かめる
            {
                primeNumber[count]=check;//素数を格納
                printf(" %d",check);//素数を表示
                count++;//素数の個数を増やす
            }
        }
        check+=2;
    }
    //時間測定用
    end = clock();
    printf("\n%.2f秒かかりました\n", (double)(end - start) / CLOCKS_PER_SEC);
    free(primeNumber);
}

また、これは一気にメモリを取得するので、細かく素数を求めるごとに追加していくリスト構造で作ってみました。

#include <stdio.h>
#include <stdlib.h>
//時間をカウントするために使う　時間測定用の部分がいらないなら削除可
#include <time.h>
struct Cell {
    int data;
    struct Cell * next;
};
typedef struct Cell Cell;



int main()
{
    //時間測定用
    clock_t start, end;
    start = clock();

    //本プログラム
    Cell *p;
    Cell *per=NULL;
    Cell standard;

    standard.data=2;
    standard.next=NULL;

    int check = 3;//素数かを比べる
    int count=1;//素数の個数
    printf(" 2");
    while (check < 3000000)//最大数制限3000000
    {
        per=&standard;//リストの参照位置を最初にリセット
        for(int i=0;i<count;i++)//配列を参照用
        {
            if(check%per->data==0)//素数か確かめる
            {
                break;
            }
            else if(i==count-1)//配列の最後まで割ったか確かめる
            {
                p = (Cell*)malloc( sizeof(Cell) ); // Cell型変数用のメモリ領域を取得
                if(p==NULL)
                {

                    printf("メモリ確保失敗");
                    return 0;//強制終了
                }
                p->data=check;//素数を格納
                p->next=NULL;
                printf(" %d",check);//素数を表示
                count++;//素数の個数を増やす
                per->next=p;//リストの最後に素数を追加
                break;
            }


        }
        check+=2;
    }
    //時間測定用
    end = clock();
    printf("\n%.2f秒かかりました\n", (double)(end - start) / CLOCKS_PER_SEC);
}

終わりに

今回プログラムを作る前から素数で割った方が早いとは思っていましたが、約１３倍もの差が出て思っていたよりも大きく、結果を出すプロセスを適当にしてはいけないことがわかりました。
これ以上を求める方はmallocの求めるやつを使い仮想メモリを2Tbyteぐらい入れていただき限界を挑戦していただきたいです。

ここまでご覧になっていただきありがとうございました。