【C言語】配列を使って素数を求める方法を解説

2023-09-132024-07-22

この記事では、C言語を使って素数を効率的に見つける方法を学びます。

特に「エラトステネスの篩(ふるい)」という古代から伝わるシンプルで強力なアルゴリズムを使って、配列を利用して素数を求める手順を詳しく解説します。

初心者の方でも理解しやすいように、具体的なコード例や実行結果を交えながら説明しますので、ぜひ一緒に学んでいきましょう。

目次から探す

素数を求めるアルゴリズム

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

例えば、2, 3, 5, 7, 11などが素数に該当します。

素数を効率的に求めるためのアルゴリズムはいくつか存在しますが、その中でも特に有名で効率的な方法の一つが「エラトステネスの篩(ふるい)」です。

エラトステネスの篩(ふるい)とは

エラトステネスの篩は、紀元前3世紀のギリシャの数学者エラトステネスによって考案された素数を求めるためのアルゴリズムです。

この方法は、ある範囲内の全ての自然数から素数を効率的に見つけ出すことができます。

エラトステネスの篩の基本的な考え方は、まず2から始めて、その倍数をすべて取り除くことです。

次に、残った数の中で最小の数を見つけ、その倍数を取り除くという操作を繰り返します。

これにより、最終的に残った数が素数となります。

エラトステネスの篩の基本的な流れ

エラトステネスの篩の具体的な手順は以下の通りです。

2から始めて、指定した範囲の全ての数をリストに並べます。
リストの中で最小の数(最初は2)を素数として記録します。
その数の倍数をリストから取り除きます。
リストの中で次に小さい数を見つけ、それを素数として記録します。
その数の倍数をリストから取り除きます。
上記の手順を繰り返し、リストの中に数が残らなくなるまで続けます。

この方法により、指定した範囲内の全ての素数を効率的に求めることができます。

エラトステネスの篩の計算量

エラトステネスの篩の計算量は、O(n log log n)です。

ここで、nは範囲の上限を示します。

この計算量は、他の素数判定アルゴリズムと比較して非常に効率的です。

具体的には、エラトステネスの篩は各数の倍数を取り除く操作を行うため、全体の計算量は範囲の上限に対して対数的に増加します。

これにより、大きな範囲の素数を求める場合でも、比較的短時間で結果を得ることができます。

エラトステネスの篩は、そのシンプルさと効率性から、素数を求めるための基本的なアルゴリズムとして広く利用されています。

次のセクションでは、このアルゴリズムをC言語でどのように実装するかについて詳しく解説します。

C言語での実装方法

ここでは、エラトステネスの篩をC言語で実装する方法について詳しく解説します。

具体的なコード例を交えながら、各ステップを順を追って説明します。

必要なヘッダファイル

C言語でプログラムを作成する際には、標準ライブラリを利用するためにヘッダファイルをインクルードする必要があります。

エラトステネスの篩を実装するために必要なヘッダファイルは以下の通りです。

#include <stdio.h>  // 標準入出力を使用するため
#include <stdbool.h> // ブール型を使用するため

配列の宣言と初期化

エラトステネスの篩では、素数かどうかを判定するために配列を使用します。

ここでは、100以下の素数を求める例を示します。

#define MAX 100  // 素数を求める範囲の最大値
bool isPrime[MAX + 1];  // 素数かどうかを判定するための配列

配列のサイズは MAX + 1 とし、インデックスが0からMAXまでの範囲をカバーします。

エラトステネスの篩の実装

エラトステネスの篩の実装は以下の3つのステップに分けられます。

配列の初期化

まず、配列を初期化します。

すべての要素を true に設定し、後で素数でないと判定された要素を false に変更します。

for (int i = 0; i <= MAX; i++) {
    isPrime[i] = true;  // 初期化
}
isPrime[0] = isPrime[1] = false;  // 0と1は素数ではない

素数の判定と配列の更新

次に、エラトステネスの篩のアルゴリズムに従って、素数でない数を配列から除外します。

for (int i = 2; i * i <= MAX; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= MAX; j += i) {
            isPrime[j] = false;  // iの倍数は素数ではない
        }
    }
}

結果の出力

最後に、配列の中で true のまま残っている要素のインデックスが素数です。

これを出力します。

for (int i = 2; i <= MAX; i++) {
    if (isPrime[i]) {
        printf("%d ", i);  // 素数を出力
    }
}
printf("\n");

完全なコード例

以上のステップをまとめると、以下のような完全なコードになります。

#include <stdio.h>
#include <stdbool.h>
#define MAX 100
int main() {
    bool isPrime[MAX + 1];
    // 配列の初期化
    for (int i = 0; i <= MAX; i++) {
        isPrime[i] = true;
    }
    isPrime[0] = isPrime[1] = false;
    // エラトステネスの篩の実装
    for (int i = 2; i * i <= MAX; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= MAX; j += i) {
                isPrime[j] = false;
            }
        }
    }
    // 結果の出力
    for (int i = 2; i <= MAX; i++) {
        if (isPrime[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");
    return 0;
}

このコードを実行すると、100以下の素数がすべて出力されます。

エラトステネスの篩を使うことで、効率的に素数を求めることができます。

応用例

大きな範囲の素数を求める

エラトステネスの篩を使って大きな範囲の素数を求める場合、配列のサイズが非常に大きくなることがあります。

例えば、1億までの素数を求める場合、1億個の要素を持つ配列が必要です。

このような大きな配列を扱う際には、メモリの確保や処理速度に注意が必要です。

以下に、1億までの素数を求めるC言語のサンプルコードを示します。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 100000000
int main() {
    bool *is_prime = malloc(MAX * sizeof(bool));
    if (is_prime == NULL) {
        printf("メモリの確保に失敗しました。\n");
        return 1;
    }
    for (int i = 0; i < MAX; i++) {
        is_prime[i] = true;
    }
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAX; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAX; j += i) {
                is_prime[j] = false;
            }
        }
    }
    for (int i = 2; i < MAX; i++) {
        if (is_prime[i]) {
            printf("%d\n", i);
        }
    }
    free(is_prime);
    return 0;
}

このコードでは、malloc関数を使って動的にメモリを確保しています。

これにより、大きな配列を扱うことが可能になります。

メモリ効率の改善

エラトステネスの篩を使う際、メモリ効率を改善する方法としてビット配列を使用することが考えられます。

ビット配列を使うことで、メモリ使用量を大幅に削減できます。

以下に、ビット配列を使ったエラトステネスの篩のサンプルコードを示します。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100000000
int main() {
    unsigned char *is_prime = malloc((MAX / 8) + 1);
    if (is_prime == NULL) {
        printf("メモリの確保に失敗しました。\n");
        return 1;
    }
    memset(is_prime, 0xFF, (MAX / 8) + 1);
    is_prime[0] &= ~0x3; // 0と1を非素数に設定
    for (int i = 2; i * i < MAX; i++) {
        if (is_prime[i / 8] & (1 << (i % 8))) {
            for (int j = i * i; j < MAX; j += i) {
                is_prime[j / 8] &= ~(1 << (j % 8));
            }
        }
    }
    for (int i = 2; i < MAX; i++) {
        if (is_prime[i / 8] & (1 << (i % 8))) {
            printf("%d\n", i);
        }
    }
    free(is_prime);
    return 0;
}

このコードでは、ビット操作を使ってメモリ効率を改善しています。

is_prime配列の各ビットが素数かどうかを示しています。