【C言語】素数判定を行う

C言語での素数の判定方法の解説ページアイキャッチ

SHARE

このページにはプロモーションが含まれています

このページでは、C言語で「数値を素数判定する方法」について解説していきます。

C言語を最近始めた方でも分かるように、とにかく詳しく書いてます！

素数判定の仕方

まず、素数の定義は下記となります（Wikipedia から引用）。

素数とは、2 以上の自然数で、正の約数が 1 と自分自身のみであるもののことである

引用元：Wikipedia

「素数である」条件と「素数でない」条件

簡単に言えば、下記の２つ両方を満たす場合、自然数 n は「素数である」と判定できます。

  • n は 2 以上である
  • n は 2 〜 n - 1 の全ての整数で割り切れない

もし、上記の２つのうち、どちらか一方でも満たさない場合、自然数 n は「素数でない」と判定することが出来ます。

論理を反転すれば、下記の２つのどちらかを満たす場合、自然数 n を「素数でない」と判定することができることになります。こっちで考えた方が素数判定のプログラムは作りやすいです。

  • n は 2 未満である
  • n は 2 〜 n - 1 のいずれかの整数で割り切れる

スポンサーリンク

「割り切れる」とは

また「割り切れる」とは、要は割り算を行なった時に「余りが 0 になる」ことを言いますので、C言語であれば剰余演算によって「割り切れる」かどうかを判断することが出来ることになります。

例えば n が i で割り切れるかどうかは、n % i の結果が 0 になるかどうかで判断できます。逆に、n % i の結果が 0 以外の値となった場合は n は i で割り切れないことになります。

剰余演算の繰り返しで素数判定を行う

つまり、自然数 n の素数判定は、i を 2 〜 n - 1 まで 1 ずつ変化させながら n % i を繰り返し計算していくことで実現することが出来ます。

もし１回でも n % i の計算結果が 0 以外になった場合は「素数でない」と判定します。逆に１回も n % i の計算結果が 0 以外にならなかった場合は「素数である」と判定します。

例えば n が 7 の場合は、下の図のように i を 2 〜 6 まで変化させながら 7 % i の計算を行います。この場合、7 % i が 0 になることはないので、7 は「素数である」と判定できます。

2からn-1までの整数との剰余算を行う様子（素数である場合）

また、例えば n が 9 の場合は、下の図のように i を 2 〜 8 まで変化させながら 9 % i の計算を行います。この場合、i が 3 の時に 9 % i が 0 になるので、9 は「素数でない」と判定できます。

2からn-1までの整数との剰余算を行う様子（素数でない場合）

n が 2 〜 n - 1 のいずれかの整数で割り切れた場合は n は「素数でない」ことになりますので、一度でも剰余演算結果が 0 になったのであれば、それ以降の剰余演算の結果に関わらず「素数でない」と判定できます。

したがって、剰余演算結果が 0 になった場合は以降の剰余演算を中止し、直ちに「素数でない」と判定してしまって良いです。

例えば、上記の n が 9 の場合は、i が 4 以降の剰余演算は行う必要はないです。

2 未満の自然数は「素数でない」と判定

また、ここまで「素数でない」と判定するための条件のうち、下記の後者の方について重点的に解説してきましたが、前者の条件にもあるように、自然数 n が 2 未満の場合は素数ではありません。

  • n は 2 未満である
  • n は 2 〜 n - 1 のいずれかの整数で割り切れる

したがって、自然数 n が 2 未満の場合は剰余演算を行うまでもなく「素数でない」と判定することが出来ます。

スポンサーリンク

素数判定を行う

ここまでの解説を踏まえ、次は実際にC言語で素数判定を行なっていきましょう！

素数判定を行う関数

ここまでの解説を踏まえて作成した素数判定を行う関数 isPrimeNumber は下記のようになります。

素数判定を行う関数 
/* nが素数であるかどうかを判定する */
int isPrimeNumber(unsigned int n) {

    unsigned int i;

    if (n < 2) {
        /* 2未満の場合は素数でない */
        return 0;
    }

    /* nが2〜n-1で割り切れるかどうかを確認 */
    for (i = 2; i < n; i++) {
        if (n % i == 0) {
            /* 2〜n-1で割り切れる場合はnは素数でない */
            return 0;
        }
    }

    return 1;
}

isPrimeNumber は、引数 n が素数である場合は 1 を、素数でない場合は 0 を返却します。

for ループの中で i を 2 〜 n - 1 まで 1 ずつ変化させながら n % i を計算しており、１回でも n % i が 0 になった場合は「素数でない」と判定し、return 0 を実行して関数を終了するようにしています。

ですので、もし for ループが完走した場合は、n が 2 〜 n - 1 の全ての整数において割り切れなかったことになります（一度も n % i == 0 が成立しなかった）。そのため、この場合は「素数である」と判定して 1 を返却するようにしています。

また、n が 2 未満である場合は素数ではあり得ないので、関数の最初で n < 2 であるかどうかを判断し、成立する場合は「素数でない」と判定して 0 を返却して直ちに関数を終了しています。

ちなみに、for (i = 2; i < n; i++) の箇所を下記のように書いてしまうと上手く素数判定出来なくなるので注意してください。

  • for (i = 0; i < n; i++)：n % 0 が実行され、ゼロ除算が発生する
  • for (i = 1; i < n; i++)：n % 1 実行され、必ず「素数でない」と判定される
  • for (i = 2; i <= n; i++)：n % n 実行され、必ず「素数でない」と判定される

素数判定を行う関数（bool 利用）

もし、stdbool.h をインクルード可能である環境であれば、下記のように引数 n が素数である場合に true を、素数でない場合は false を返却するようにする事もできます。おそらくこっちの方がソースコードが読みやすいと思います。

素数判定を行う関数(bool) 
#include <stdbool.h>

/* nが素数であるかどうかを判定する */
bool isPrimeNumber(unsigned int n) {

    unsigned int i;

    if (n < 2) {
        /* 2未満の場合は素数でない */
        return false;
    }

    /* nが2〜n-1で割り切れるかどうかを確認 */
    for (i = 2; i < n; i++) {
        if (n % i == 0) {
            /* 2〜n-1で割り切れる場合はnは素数でない */
            return false;
        }
    }

    return true;
}

素数判定を行う関数 で紹介した isPrimeNumber 関数から、0 を返却していた箇所を false を返却するように変更し、さらに 1 を返却していた箇所を true を返却するように変更しています。

スポンサーリンク

main 関数で素数判定を行う

わざわざ関数化したくないような場合は、下記のように main 関数を記述してやれば良いです。

素数判定を行うmain関数 
#include <stdio.h>

int main(void) {
    unsigned int n; /* 自然数 */
    int is_prime_num; /* 素数かどうか */
    unsigned int i;

    /* 素数判定を行う自然数を設定 */
    n = 102;

    /* 素数であると仮定 */
    is_prime_num = 1;

    if (n < 2) {
        /* 2未満の場合は素数でない */
        is_prime_num = 0;
    }

    /* nが2〜n-1で割り切れるかどうかを確認 */
    for (i = 2; i < n; i++) {
        if (n % i == 0) {
            /* 2〜n-1で割り切れる場合はnは素数でない */
            is_prime_num = 0;
        }
    }

    /* 素数判定結果を表示 */
    if (is_prime_num) {
        printf("%d is a PRIME NUMBER\n", n);
    } else {
        printf("%d is NOT a prime number\n", n);
    }

    return 0;
}

is_prime_num が「n の素数判定結果を格納する変数」になっています（素数である場合は 1、素数でない場合は 0）。

まず n は素数であると仮定して is_prime_num に 1 を格納しておき、素数でないと分かった際に is_prime_num に 0 を格納するようにしています。

関数の時とは異なり、n が素数でないと分かったといって return してしまうとプログラムが終了してしまうので注意が必要です。

ちなみに、上記の main 関数では n % i == 0 が成立して素数でないと分かった場合でも for ループが継続して実行されます。素数でないと分かった後も for ループが実行されてしまい無駄な処理が多いです。

これは、下記のように for ループ内の処理を書き換えることで改善することが出来ます。

breakの導入 
/* nが2〜n-1で割り切れるかどうかを確認 */
for (i = 2; i < n; i++) {
    if (n % i == 0) {
        /* 2〜n-1で割り切れる場合はnは素数でない */
        is_prime_num = 0;
        break;
    }
}

for ループ内で break を実行すれば、即座に for ループを終了することが出来ます。したがって、上記のように break を実行することで、素数でないと分かった時に即座にループを終了し、以降の無駄な剰余演算や比較をスキップすることが出来ます。

素数判定の実行例

ここまでで、C言語で素数判定を行う方法の解説は終了です。

最後に、素数判定を行う関数 で紹介した isPrimeNumber 関数を利用して、下記を行うプログラムの例を紹介しておきます。

  • 特定の整数以下の素数を全て表示する
  • 特定の整数以下の素数の数を数える

特定の整数以下の素数を全て表示する

下記は、素数判定を行う関数 で紹介した isPrimeNumber 関数を利用した、ユーザーに入力された整数以下の素数を全て表示するプログラムの例となります。

素数を表示する 
#include <stdio.h>

/* nが素数であるかどうかを判定する */
int isPrimeNumber(unsigned int n) {

    unsigned int i;

    if (n < 2) {
        /* 2未満の場合は素数でない */
        return 0;
    }

    /* nが2〜n-1で割り切れるかどうかを確認 */
    for (i = 2; i < n; i++) {
        if (n % i == 0) {
            /* 2〜n-1で割り切れる場合はnは素数でない */
            return 0;
        }
    }

    return 1;
}

int main(void) {
    unsigned int i;
    unsigned int num;

    printf("num:");
    scanf("%d", &num);

    for (i = 0; i <= num; i++) {
        if (isPrimeNumber(i)) {
            /* iが素数の場合のみ表示する */
            printf("%d,", i);
        }
    }
    printf("\n");

    return 0;
}

プログラムを実行して 97 を入力してエンターキーを押せば、下記のように 97 以下の素数全てが表示されます。

num:97
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,

入力される整数が大きすぎるとプログラムが終わらなくなるので注意してください。

スポンサーリンク

特定の整数以下の素数の数を数える

下記は、素数判定を行う関数 で紹介した isPrimeNumber 関数を利用した、ユーザーに入力された整数以下の素数の数を数えるプログラムの例となります。

素数の数を数える 
#include <stdio.h>

/* nが素数であるかどうかを判定する */
int isPrimeNumber(unsigned int n) {

    unsigned int i;

    if (n < 2) {
        /* 2未満の場合は素数でない */
        return 0;
    }

    /* nが2〜n-1で割り切れるかどうかを確認 */
    for (i = 2; i < n; i++) {
        if (n % i == 0) {
            /* 2〜n-1で割り切れる場合はnは素数でない */
            return 0;
        }
    }

    return 1;
}

int main(void) {
    unsigned int i;
    unsigned int num;
    unsigned int count;

    printf("num:");
    scanf("%d", &num);

    count = 0;

    for (i = 0; i <= num; i++) {
        if (isPrimeNumber(i)) {
            /* iが素数の場合のみカウントアップする */
            count++;
        }
    }
    
    printf("%d\n", count);
    
    return 0;
}

プログラムを実行して 97 を入力してエンターキーを押せば、下記のように 97 以下の素数の数が表示されます。

num:97
25

こちらも入力される整数が大きすぎるとプログラムが終わらなくなるので注意してください。

まとめ

このページでは、C言語で「数値の素数判定を行う方法」について解説しました！

要は、下記の２つの条件のいずれかが成立する場合に、数値を「素数でない」と判定すれば良いです。

  • n は 2 未満である
  • n は 2 〜 n - 1 のいずれかの整数で割り切れる

逆に、上記の２つの条件の両方が成立しない場合、数値は「素数である」と判定できます。

また、このページの最初にも説明した通り、下記の２つ両方を満たす場合に自然数 n を「素数である」と判定する事も可能です。

  • n は 2 以上である
  • n は 2 〜 n - 1 の全ての整数で割り切れない

この場合、ストレートに上記に当てはめて素数判定を行う関数を書いた場合、下記のようになるかなぁと思います。

素数判定を行う関数の別解 
/* nが素数であるかどうかを判定する */
int isPrimeNumber(unsigned int n) {

    unsigned int i;
    unsigned int sum;

    if (n >= 2) {
        /* 2以上の場合 */

        sum = 0;

        /* nが2〜n-1の全てで割り切れないかどうかを確認 */
        for (i = 2; i < n; i++) {
            if (n % i != 0) {
                /* 割り切れなかった個数を数える */
                sum++;
            }
        }

        if (sum == n - 2) {
            /* nが2〜n-1の全てで割り切れなかった場合 */

            /* 素数であると判定 */
            return 1;
        }
    }

    return 0;
}

素数判定を行う関数 で紹介した isPrimeNumber 関数と比べると、おそらく上記の関数の方がわかりにくいと思う人が多いんじゃないかなぁと思うんですよね。少なくともこっちの方が処理は遅いです。

上記の関数と 素数判定を行う関数 で紹介した isPrimeNumber 関数とは、判定を行う時の論理を反転させているだけです。いずれにしても正しく素数判定は行えます。

つまり、私が言いたいことは、何かを判定する際には “論理を反転させることで簡単に処理が書ける可能性がある” という事です。特に判定時の条件が複数ある場合は、論理の反転によってプログラムが簡単に書ける事も多いです。

いろんな判定を行うプログラムを書いていくことでこの辺りも慣れていくと思いますので、今回紹介した素数判定だけでなく、いろんな判定プログラムの作成にチャレンジしてみてください！

また、今回紹介した素数の判定アルゴリズムは一番簡単なものを用いており処理は遅いです。もっと速く素数判定を行うアルゴリズムもたくさん考案されていますので、興味がある方はググってみると良いと思います！

オススメの参考書（PR）

C言語学習中だけど分からないことが多くて挫折しそう...という方には、下記の「スッキリわかるC言語入門」がオススメです！

スッキリわかるC言語入門 第2版
posted with ヨメレバ
中山 清喬/株式会社フレアリンク インプレス 2021年12月14日頃
楽天ブックス
Amazon
Kindle
 

まず学習を進める上で、参考書は２冊持っておくことをオススメします。この理由は下記の２つです。

  • 参考書によって、解説の仕方は異なる
  • 読み手によって、理解しやすい解説の仕方は異なる

ある人の説明聞いても理解できなかったけど、他の人からちょっと違った観点での説明を聞いて「あー、そういうことね！」って簡単に理解できた経験をお持ちの方も多いのではないでしょうか？

それと同じで、１冊の参考書を読んで理解できない事も、他の参考書とは異なる内容の解説を読むことで理解できる可能性があります。

なので、参考書は２冊持っておいた方が学習時に挫折しにくいというのが私の考えです。

特に上記の「スッキリわかるC言語入門」は、他の参考書とは違った切り口での解説が豊富で、他の参考書で理解できなかった内容に対して違った観点での解説を読むことができ、オススメです。題名の通り「なぜそうなるのか？」がスッキリ理解できるような解説内容にもなっており、C言語入門書としてもかなり分かりやすい参考書だと思います。

もちろんネット等でも色んな観点からの解説を読むことが出来ますので、分からない点は別の人・別の参考書の解説を読んで解決していきましょう！もちろん私のサイトも参考にしていただけると嬉しいです！

入門用のオススメ参考書は下記ページでも紹介していますので、こちらも是非参考にしていただければと思います。

https://daeudaeu.com/c_reference_book/

同じカテゴリのページ一覧を表示

前の記事

C言語で重複なしの乱数を生成する方法解説ページアイキャッチ
【C言語】重複なしで乱数を生成する方法

次の記事

【C言語】最大値と最小値を求める方法
C言語における最大値と最小値の求め方の解説ページアイキャッチ