【C言語】n番目の素数を求めるプログラムを書いてみよう

C

C言語で遊んでみたい!

素数判定がしたい!(?)

そんな悩みにお答えします。

今回はC言語でn番目の素数を求めるプログラムを紹介・解説します。

この記事の内容
  • C言語の基本
  • 素数判定のアルゴリズム

この記事に需要はほぼありませんが、春休みの息抜きにやってみてください。

環境

gccを使ってコンパイルしています。

c言語がコンパイル・実行できる環境であれば可能です。

ソースコード

注意

今回紹介するのは、n番目の素数を求めるプログラムです。

  • n個の素数を求めるプログラムでもあります。
  • nまでの素数を求めるプログラムではありません。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int IsPrime(int n, int cnt, int *primes) { //素数判定の関数
    for (int i = 0; i < cnt; i++) {
        if (n % primes[i] == 0) {
            //素数じゃない
            return 0;
        }
    }
    //素数
    return 1;
}

int main(int argc, char* argv[]) {
    int num = atoi(argv[1]); //入力された文字を数字に変換
    int primes[num]; //長さがnの素数リストを宣言
    primes[0] = 2; //最初の素数である2を入れておく
    int cnt = 1; //リストの長さを表す変数
    printf("2\n");
    for (int i = 3; cnt <  num; i += 2) { //配列が埋まるまでループ
        if (IsPrime(i, cnt, primes)) { //素数判定
            primes[cnt] = i; //素数リストに追加
            cnt++; //リストの長さを+1する
            printf("%d\n", i);
        }
    }
}

使い方

コンパイルして実行します。

gcc -o primenumber primenumber.c
./primenumber 10
2
3
5
7

解説

変数やループの意味については、コメントアウトで書かれている通りです。

IsPrime()は素数かどうかを判定する関数です。

このプログラムでは、「素数リスト」が重要なアイテムとなっています。

処理の流れ

流れとしては、

  1. 「ある数」が素数か?を素数リストを使って判定
  2. 素数なら素数リストに追加
  3. 「ある数」を2ずつ増やす(3,5,7…)

求めたいのはn番目の素数です。

n番目の素数は、長さがnの素数リストの最後の数となります。

つまり、素数リストの長さがnになるまで、リストに素数を追加し続けているというわけです。

素数判定の仕組み

IsPrime関数の仕組みを解説します。

自然数は、すべて素数の積で表すことができます。=>素因数分解
しかし素数は、素因数分解できません。

つまり、その数より小さいのすべての素数で割り切ることができなければ、素数であるといえます。

例えば

23が素数かどうかを判定したければ、23未満の素数「2,3,5,7,11,13,17,19」で割り切れるかどうかを確かめます。

この場合「23未満の素数」は素数リストに入っています。

そして、その数が素数であれば、(23を)素数リストに追加します。

これが素数判定の仕組みです。

高速化

先ほど、「その数より小さいのすべての素数で割り切ることができなければ、素数である」と言いましたが、実はすべての素数である必要はありません。

半分より大きい数では割れない

23なら「2,3,5,7,11,13,17,19」割り切れるか確かめます。

この時、「13,17,19」で割り切れないことは明らかですよね。
なぜなら23の半分より大きいからです。

よって、11.5未満の素数でのみ確かめれば良いので、時間が短縮されます。

int IsPrime(int n, int cnt, int *primes) { //素数判定の関数
    for (int i = 0; i < primes[i] / 2; i++) {
        if (n % primes[i] == 0) {
            //素数じゃない
            return 0;
        }
    }
    //素数
    return 1;
}

さらに高速化

100を素数判定するとします。

先ほどの通りにやると50未満の素数で確かめることになりますが、もっと短縮できます。

例えば25で割るとき、25 × 4で割り切れるため、素数ではないと分かります。

勘の良い方なら気づくと思いますが、100は25 × 4 = 4 × 25 なので、4で割る作業と同じということがわかります。

同様に、20 × 5 = 5 × 20 なので、5で割る作業だけで十分です。

502
402.5
303.33…
254
205
156.66…
128.33..
1010
左の数で割ることは、右の数で割ることと同じ

下にいくにつれて近い値になっているのがわかります。

つまり、両方の数が同じになった「10」より大きい数で割るのは意味がないので、10以下の数のみ足しかめれば良いことになります。

100 = 10 × 10 のように、ふたつ掛け合わせた数を求めるには、平方根(ルート)を使います。

int IsPrime(int n, int cnt, int *primes) { //素数判定の関数
    for (int i = 0; i < sqrt(primes[i]); i++) {
        if (n % primes[i] == 0) {
            //素数じゃない
            return 0;
        }
    }
    //素数
    return 1;
}

いかがだったでしょうか。

いつもの記事とは全く違った内容になってしまいましたが、最後まで読んでいただきありがとうございました。

質問等あれば、コメントまでよろしくお願いします。

コメント