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

素数とは、1とその数自身以外に約数を持たない自然数のことです。C言語で数値が素数かどうかを判定するには、基本的な方法として、2からその数の平方根までの整数で割り切れるかどうかを確認します。

この方法は、数値を効率的にチェックするために用いられます。ループを使用して、割り切れるかどうかを確認し、割り切れる場合は素数ではないと判定します。

このアルゴリズムは、特に大きな数に対しても効率的に動作するため、素数判定において一般的に使用されます。

この記事でわかること

C言語での基本的な素数判定プログラムの実装方法
素数判定プログラムの最適化手法とその効果
素数を用いた暗号化技術や乱数生成の応用例
素数判定の効率的なアルゴリズムの選択方法

目次から探す

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

基本的な素数判定プログラムの例

素数とは、1とその数自身以外に約数を持たない自然数のことです。

C言語で素数を判定する基本的なプログラムを以下に示します。

#include <stdio.h>
int main() {
    int number, i;
    int isPrime = 1; // 素数であると仮定
    printf("整数を入力してください: ");
    scanf("%d", &number);
    if (number <= 1) {
        isPrime = 0; // 1以下は素数ではない
    } else {
        for (i = 2; i < number; i++) {
            if (number % i == 0) {
                isPrime = 0; // 割り切れる場合は素数ではない
                break;
            }
        }
    }
    if (isPrime) {
        printf("%dは素数です。\n", number);
    } else {
        printf("%dは素数ではありません。\n", number);
    }
    return 0;
}

整数を入力してください: 7
7は素数です。

このプログラムは、入力された整数が素数かどうかを判定します。

2からその数の1つ手前までの整数で割り切れるかを確認し、割り切れる場合は素数ではないと判断します。

ループを用いた素数判定

ループを用いることで、素数判定の効率を上げることができます。

以下のプログラムでは、ループの範囲を最適化しています。

#include <stdio.h>
#include <math.h>
int main() {
    int number, i;
    int isPrime = 1; // 素数であると仮定
    printf("整数を入力してください: ");
    scanf("%d", &number);
    if (number <= 1) {
        isPrime = 0; // 1以下は素数ではない
    } else {
        for (i = 2; i <= sqrt(number); i++) {
            if (number % i == 0) {
                isPrime = 0; // 割り切れる場合は素数ではない
                break;
            }
        }
    }
    if (isPrime) {
        printf("%dは素数です。\n", number);
    } else {
        printf("%dは素数ではありません。\n", number);
    }
    return 0;
}

整数を入力してください: 10
10は素数ではありません。

このプログラムでは、ループの上限を入力された数の平方根までにすることで、計算量を減らしています。

これにより、より効率的に素数判定が可能です。

関数を用いた素数判定

素数判定を関数化することで、コードの再利用性を高めることができます。

以下に関数を用いた例を示します。

#include <stdio.h>
#include <math.h>
// 素数判定関数
int isPrime(int number) {
    if (number <= 1) return 0; // 1以下は素数ではない
    for (int i = 2; i <= sqrt(number); i++) {
        if (number % i == 0) return 0; // 割り切れる場合は素数ではない
    }
    return 1; // 素数である
}
int main() {
    int number;
    printf("整数を入力してください: ");
    scanf("%d", &number);
    if (isPrime(number)) {
        printf("%dは素数です。\n", number);
    } else {
        printf("%dは素数ではありません。\n", number);
    }
    return 0;
}

整数を入力してください: 13
13は素数です。

このプログラムでは、isPrime関数を用いて素数判定を行っています。

関数化することで、他のプログラムでも簡単に素数判定を利用することができます。

素数判定プログラムの最適化

素数判定は、特に大きな数に対しては計算量が増大するため、効率的なアルゴリズムが求められます。

ここでは、素数判定を最適化するためのいくつかの手法を紹介します。

エラトステネスの篩を用いた最適化

エラトステネスの篩(ふるい)は、2から始めて順に倍数を消していくことで素数を見つける古典的なアルゴリズムです。

この方法は、特に多くの素数を一度に求める場合に有効です。

#include <stdio.h>
#include <string.h>
#define MAX 100
void sieveOfEratosthenes(int n) {
    int isPrime[MAX];
    memset(isPrime, 1, sizeof(isPrime)); // すべての数を素数と仮定
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = 0; // 素数ではない
            }
        }
    }
    printf("素数: ");
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");
}
int main() {
    int n = 30;
    printf("%dまでの素数をエラトステネスの篩で求めます。\n", n);
    sieveOfEratosthenes(n);
    return 0;
}

30までの素数をエラトステネスの篩で求めます。
素数: 2 3 5 7 11 13 17 19 23 29

このプログラムは、指定された範囲内の素数を効率的に求めます。

エラトステネスの篩は、特に小さな数の範囲で多くの素数を求める際に非常に効果的です。

試し割り法の効率化

試し割り法は、素数判定の基本的な方法ですが、効率化することで計算量を減らすことができます。

以下のプログラムでは、偶数を除外し、3以上の奇数のみをチェックすることで効率化を図っています。

#include <stdio.h>
#include <math.h>
int isPrimeOptimized(int number) {
    if (number <= 1) return 0; // 1以下は素数ではない
    if (number == 2) return 1; // 2は素数
    if (number % 2 == 0) return 0; // 偶数は素数ではない
    for (int i = 3; i <= sqrt(number); i += 2) {
        if (number % i == 0) return 0; // 割り切れる場合は素数ではない
    }
    return 1; // 素数である
}
int main() {
    int number = 29;
    if (isPrimeOptimized(number)) {
        printf("%dは素数です。\n", number);
    } else {
        printf("%dは素数ではありません。\n", number);
    }
    return 0;
}

29は素数です。

このプログラムでは、偶数を除外し、3以上の奇数のみをチェックすることで、計算量を半分に削減しています。

これにより、より効率的に素数判定が可能です。

メモ化による計算の高速化

メモ化は、計算結果を保存して再利用することで、重複する計算を避ける手法です。

素数判定においても、既に判定済みの数を保存することで効率化が可能です。

#include <stdio.h>
#include <math.h>
#define MAX 1000
int memo[MAX];
int isPrimeMemoized(int number) {
    if (number <= 1) return 0; // 1以下は素数ではない
    if (memo[number] != -1) return memo[number]; // 既に判定済み
    if (number == 2) return memo[number] = 1; // 2は素数
    if (number % 2 == 0) return memo[number] = 0; // 偶数は素数ではない
    for (int i = 3; i <= sqrt(number); i += 2) {
        if (number % i == 0) return memo[number] = 0; // 割り切れる場合は素数ではない
    }
    return memo[number] = 1; // 素数である
}
int main() {
    memset(memo, -1, sizeof(memo)); // メモを初期化
    int number = 31;
    if (isPrimeMemoized(number)) {
        printf("%dは素数です。\n", number);
    } else {
        printf("%dは素数ではありません。\n", number);
    }
    return 0;
}