【C言語】数値が素数かどうか判定する方法を解説

2023-09-132024-07-23

この記事では、C言語を使って数値が素数かどうかを判定する方法について解説します。

素数判定の基本的なプログラム構造から、試し割り法やエラトステネスの篩といった具体的なアルゴリズムの実装方法まで、初心者でも理解しやすいように説明します。

また、大きな数の素数判定や素数列の生成についても触れ、効率的なアルゴリズムの選択や実装方法を紹介します。

目次から探す

C言語での素数判定プログラムの実装

素数判定は、与えられた数値が素数であるかどうかを確認するための基本的なプログラミング課題です。

C言語を使って素数判定を行う方法を、基本的なプログラム構造から具体的なアルゴリズムの実装まで詳しく解説します。

基本的なプログラム構造

まず、C言語でプログラムを作成する際の基本的な構造について説明します。

インクルードファイルとマクロ定義

C言語のプログラムでは、標準ライブラリを使用するためにインクルードファイルを指定します。

また、必要に応じてマクロ定義を行います。

#include <stdio.h>
#include <math.h> // sqrt関数を使用するために必要
#define TRUE 1
#define FALSE 0

メイン関数の構成

メイン関数はプログラムのエントリーポイントです。

ここでは、ユーザーからの入力を受け取り、素数判定関数を呼び出して結果を表示します。

int main() {
    int number;
    printf("素数判定を行う数値を入力してください: ");
    scanf("%d", &number);
    if (is_prime(number)) {
        printf("%d は素数です。\n", number);
    } else {
        printf("%d は素数ではありません。\n", number);
    }
    return 0;
}

試し割り法による素数判定の実装

試し割り法は、与えられた数値を2からその平方根までの整数で割り切れるかどうかを確認する方法です。

関数の定義

まず、素数判定を行う関数 is_prime を定義します。

int is_prime(int num) {
    if (num <= 1) return FALSE; // 1以下の数は素数ではない
    if (num == 2) return TRUE;  // 2は素数
    if (num % 2 == 0) return FALSE; // 偶数は素数ではない

ループと条件分岐の使用

次に、2から平方根までの整数で割り切れるかどうかを確認します。

for (int i = 3; i <= sqrt(num); i += 2) {
        if (num % i == 0) return FALSE;
    }
    return TRUE;
}

√nまでのループの実装

上記のコードでは、ループの上限を sqrt(num) とし、奇数のみをチェックすることで効率を上げています。

エラトステネスの篩による素数判定の実装

エラトステネスの篩は、複数の数値に対して効率的に素数判定を行うアルゴリズムです。

配列の初期化

まず、指定された範囲内の数値を格納する配列を初期化します。

void sieve_of_eratosthenes(int n) {
    int prime[n+1];
    for (int i = 0; i <= n; i++) {
        prime[i] = TRUE;
    }

篩のアルゴリズムの実装

次に、2から始めて、各数値の倍数を素数リストから除外します。

for (int p = 2; p * p <= n; p++) {
        if (prime[p] == TRUE) {
            for (int i = p * p; i <= n; i += p) {
                prime[i] = FALSE;
            }
        }
    }

結果の出力

最後に、素数リストを出力します。

printf("素数: ");
    for (int p = 2; p <= n; p++) {
        if (prime[p] == TRUE) {
            printf("%d ", p);
        }
    }
    printf("\n");
}

このようにして、C言語を使って素数判定を行う方法を基本的なプログラム構造から具体的なアルゴリズムの実装まで解説しました。

試し割り法とエラトステネスの篩の両方を理解することで、効率的な素数判定プログラムを作成することができます。

素数判定プログラムの応用

大きな数の素数判定

効率的なアルゴリズムの選択

大きな数の素数判定には、効率的なアルゴリズムを選択することが重要です。

試し割り法はシンプルで理解しやすいですが、大きな数に対しては計算量が増大し、実用的ではありません。

そこで、より効率的なアルゴリズムとして「ミラー・ラビン素数判定法」や「フェルマーテスト」などが利用されます。

ミラー・ラビン素数判定法は確率的なアルゴリズムで、非常に大きな数に対しても高速に素数判定を行うことができます。

このアルゴリズムは、ある程度の確率で誤判定が発生する可能性がありますが、繰り返しテストを行うことでその確率を極めて低く抑えることができます。

メモリと計算時間の考慮

大きな数の素数判定では、メモリと計算時間のバランスを考慮する必要があります。

例えば、エラトステネスの篩を大きな数に対して適用すると、メモリ使用量が膨大になるため、現実的ではありません。

以下に、ミラー・ラビン素数判定法の簡単な実装例を示します。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 繰り返し二乗法による累乗計算
unsigned long long mod_exp(unsigned long long base, unsigned long long exp, unsigned long long mod) {
    unsigned long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp = exp >> 1;
        base = (base * base) % mod;
    }
    return result;
}
// ミラー・ラビン素数判定法
bool is_prime(unsigned long long n, int k) {
    if (n <= 1 || n == 4) return false;
    if (n <= 3) return true;
    unsigned long long d = n - 1;
    while (d % 2 == 0) {
        d /= 2;
    }
    for (int i = 0; i < k; i++) {
        unsigned long long a = 2 + rand() % (n - 4);
        unsigned long long x = mod_exp(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool continueLoop = false;
        for (unsigned long long r = d; r != n - 1; r *= 2) {
            x = (x * x) % n;
            if (x == 1) return false;
            if (x == n - 1) {
                continueLoop = true;
                break;
            }
        }
        if (!continueLoop) return false;
    }
    return true;
}
int main() {
    unsigned long long num = 104729; // 判定する数
    int k = 5; // テスト回数
    if (is_prime(num, k)) {
        printf("%lluは素数です。\n", num);
    } else {
        printf("%lluは素数ではありません。\n", num);
    }
    return 0;
}

素数列の生成

エラトステネスの篩の応用

エラトステネスの篩は、素数列を生成するための効率的なアルゴリズムです。

このアルゴリズムは、指定した範囲内の全ての素数を効率的に見つけることができます。

以下に、エラトステネスの篩を用いて素数列を生成するプログラムの例を示します。

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
void sieve_of_eratosthenes(int n) {
    bool prime[n+1];
    for (int i = 0; i <= n; i++) {
        prime[i] = true;
    }
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");
}
int main() {
    int n = 50; // 50までの素数を生成
    printf("%dまでの素数: ", n);
    sieve_of_eratosthenes(n);
    return 0;
}