C言語での素数判定アルゴリズム：効率的なプログラムの書き方と計算量

C言語は、ハードウェアに近いレイヤーで高速な処理を実現できるため、アルゴリズムの実装能力を磨くのに最適なプログラミング言語です。

数値計算の中でも「素数判定」は、計算機科学の基礎であり、効率的なコーディングの重要性を学ぶための優れた題材となります。

本記事では、C言語を用いた素数判定の基本的なプログラムから、計算量を意識した高度な最適化手法までを詳しく解説します。

パフォーマンスを最大限に引き出すための考え方を身につけ、実戦的なプログラミングスキルの向上に役立ててください。

素数判定の基本概念

素数とは、1とその数自身以外に正の約数を持たない、1より大きい自然数のことを指します。

プログラミングにおいて素数を判定する場合、対象となる数 n が他の数で割り切れるかどうかを確認する作業が中心となります。

もっとも単純な方法は、2から n-1 までのすべての整数で順に割ってみるというアプローチです。

しかし、判定する数値が大きくなればなるほど、この方法では処理時間が膨大になってしまいます。

C言語で効率的なプログラムを書くためには、数学的な性質を利用して、計算の無駄を省く工夫が必要です。

基本的な素数判定アルゴリズム（試し割り法）

まずは、アルゴリズムの原点となる「試し割り法」の基本的な実装から見ていきましょう。

O(n) の素朴な実装

もっとも直感的な方法は、for 文を使って2から順番にループを回す手法です。

この手法では、入力された数値に対して最大で n 回の比較が行われるため、計算量は O(n) となります。

#include <stdio.h>
#include <stdbool.h>

// 素数判定を行う関数
bool is_prime_basic(int n) {
    // 1以下の場合は素数ではない
    if (n <= 1) return false;

    // 2からn-1まで順に割ってみる
    for (int i = 2; i < n; i++) {
        // 割り切れたら素数ではない
        if (n % i == 0) return false;
    }
    // 最後まで割り切れなければ素数
    return true;
}

int main() {
    int num = 29;
    if (is_prime_basic(num)) {
        printf("%dは素数です。\n", num);
    } else {
        printf("%dは素数ではありません。\n", num);
    }
    return 0;
}

29は素数です。

このプログラムは正しく動作しますが、例えば n が10億を超えるような場合、10億回の演算が必要になり、現代のコンピュータでも目に見える遅延が発生します。

平方根を利用した最適化 (O(√n))

素数判定を劇的に高速化する最初の一歩は、「判定は √n まで行えば十分である」という数学的性質を利用することです。

もし n が a * b という積で表される合成数である場合、a と b のうち少なくとも一方は √n 以下になります。

この性質を利用すると、ループの回数を n から √n へと大幅に削減できます。

計算量は O(√n) となり、大規模な数値に対しても実用的な速度で動作するようになります。

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool is_prime_optimized(int n) {
    if (n <= 1) return false;
    if (n == 2) return true; // 2は唯一の偶数の素数

    // 平方根までを確認する
    // i * i <= n とすることで sqrt関数を呼び出すコストを抑える
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int num = 104729; // 10,000番目の素数
    if (is_prime_optimized(num)) {
        printf("%dは素数です。\n", num);
    }
    return 0;
}

104729は素数です。

この最適化により、100万（10^6）の判定にかかる計算回数は、100万回からわずか1000回に短縮されます。

さらなる高速化手法

特定の用途や、より高いパフォーマンスが求められる場合には、さらに工夫を凝らしたアルゴリズムが採用されます。

2以外の偶数を除外するロジック

2以外の偶数はすべて素数ではないという事実は、判定コストをさらに半分に減らすために役立ちます。

最初に n が2であるか、あるいは2で割り切れるかを確認すれば、以降のループでは奇数のみをチェックすればよくなります。

bool is_prime_fast(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false; // 2以外の偶数を除外

    // 3から奇数だけをチェックする
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

この改良により、ループのステップ数がさらに 1/2 になり、実行効率が向上します。

エラトステネスの篩による一括判定

単一の数値ではなく、ある範囲（例：1から10,000まで）に含まれる素数をすべて抽出したい場合には、「エラトステネスの篩（ふるい）」が非常に強力です。

これは、既知の素数の倍数を順番に消していくことで素数だけを残していくアルゴリズムです。

計算量は O(n log log n) と極めて高速で、大量の判定を一度に行う際に適しています。

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

void sieve_of_eratosthenes(int limit) {
    bool prime[limit + 1];
    // すべてを真（素数である候補）で初期化
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;

    for (int p = 2; p * p <= limit; p++) {
        // prime[p]がまだ書き換えられていないなら、それは素数
        if (prime[p] == true) {
            // pの倍数をすべて素数候補から外す
            for (int i = p * p; i <= limit; i += p)
                prime[i] = false;
        }
    }

    // 結果の一部を出力
    printf("%d以下の素数の一部: ", limit);
    for (int p = 2; p <= 20; p++) {
        if (prime[p]) printf("%d ", p);
    }
    printf("\n");
}

int main() {
    sieve_of_eratosthenes(1000);
    return 0;
}

1000以下の素数の一部: 2 3 5 7 11 13 17 19

エラトステネスの篩は、メモリ消費量が増えるというデメリットがありますが、速度面では他の追随を許さない効率を誇ります。

アルゴリズムの計算量と性能比較

各アルゴリズムの性能特性を理解することは、適切な実装を選択するために欠かせません。

以下の表は、それぞれの判定手法における計算量と主な用途をまとめたものです。

C言語で実用的なアプリケーションを開発する場合、基本的には平方根を利用した最適化を選択すれば間違いありません。

競技プログラミングやデータ解析などで、大量の数値を扱う場合にのみ、エラトステネスの篩を検討するのが定石です。

C言語で実装する際の注意点

C言語で素数判定プログラムを作成する際に、考慮すべき重要なポイントがいくつかあります。

1. データ型の選択

C言語の int 型は、多くの環境で32ビットであり、扱える最大値は約21億（2,147,483,647）です。

これを超える巨大な素数を扱いたい場合は、long long 型（64ビット）を使用する必要があります。

型を誤ると、バッファオーバーフローや負の値への反転が発生し、判定結果が不正になります。

2. 浮動小数点演算の回避

ループの条件式で sqrt() 関数を使用することも可能ですが、浮動小数点演算は整数演算に比べて低速です。

また、精度の問題で稀に誤差が生じる可能性も否定できません。

そのため、i * i <= n という形式で、整数同士の積を用いて判定範囲を制限するのがC言語らしい堅牢な書き方です。

3. メモリ管理

エラトステネスの篩を非常に大きな範囲で実行する場合、スタック領域に配列を確保するとスタックオーバーフローを引き起こす可能性があります。

100万を超えるような要素数を持つ配列を扱う場合は、malloc() 関数を用いた動的メモリ確保、あるいは static 変数としての定義を検討してください。

まとめ

C言語における素数判定は、単純なループ処理から、数学的根拠に基づいた最適化まで、幅広いアルゴリズムの深みを感じられるテーマです。

基本的な O(√n) の試し割り法をマスターするだけでも、多くの実務上の課題は解決できます。

しかし、計算量の違いが実行速度に与える影響を理解し、状況に応じてエラトステネスの篩などの手法を使い分けられるようになることが、プロのプログラマへの第一歩です。

本記事で紹介したコードを参考に、自分でも様々な数値を入力して、そのパフォーマンスの違いを体感してみてください。

効率的なプログラムを書く能力は、C言語だけでなく、あらゆるプログラミング言語に通ずる一生物のスキルとなるはずです。