C 言語でエラトステネスの篩をどのように実装するか

はじめに

この実験では、C 言語を使ってエラトステネスの篩アルゴリズムを実装し、与えられた上限までの素数を見つける方法を学びます。まず、ユーザーから上限を読み取り、次に素数の倍数を非素数としてマークし、最後に見つけたすべての素数を表示します。この実験では、C 言語を使って整数論と離散数学の概念を扱います。

この実験は、3 つの主なステップで構成されています。上限を読み取り、倍数を非素数としてマークし、すべての素数を表示することです。これらの手順に従うことで、エラトステネスの篩アルゴリズムとその C 言語による実装について、より深い理解を得ることができます。

上限を読み取る

このステップでは、C 言語でエラトステネスの篩アルゴリズムの上限を読み取る方法を学びます。上限は、見つけたい素数の範囲を決定します。

まず、実装用の新しい C ファイルを作成しましょう。

cd ~/project
nano prime_sieve.c

次に、上限を読み取る初期コードを書きましょう。

#include <stdio.h>

int main() {
    int upper_limit;

    printf("Enter the upper limit for finding prime numbers: ");
    scanf("%d", &upper_limit);

    printf("Upper limit entered: %d\n", upper_limit);

    return 0;
}

プログラムをコンパイルして実行します。

gcc prime_sieve.c -o prime_sieve
./prime_sieve

出力例：

Enter the upper limit for finding prime numbers: 50
Upper limit entered: 50

コードを解説しましょう。

scanf()を使ってユーザーから整数入力を読み取ります。
%dフォーマット指定子は、scanf()に整数を読み取るように指示します。
入力をupper_limit変数に格納します。
次に、入力された上限を表示して入力を確認します。

倍数を非素数としてマークする

このステップでは、エラトステネスの篩アルゴリズムの核心部分を実装し、素数の倍数を非素数としてマークします。

前のprime_sieve.cファイルを修正しましょう。

cd ~/project
nano prime_sieve.c

配列を追加して倍数をマークするようにコードを更新します。

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

int main() {
    int upper_limit;

    printf("Enter the upper limit for finding prime numbers: ");
    scanf("%d", &upper_limit);

    // 素数と非素数をマークするためのブール型配列を作成
    bool is_prime[upper_limit + 1];

    // すべての数を素数として初期化
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // 各素数の倍数を非素数としてマーク
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // p の倍数を非素数としてマーク
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    printf("Marking multiples complete.\n");

    return 0;
}

プログラムをコンパイルして実行します。

gcc prime_sieve.c -o prime_sieve
./prime_sieve

出力例：

Enter the upper limit for finding prime numbers: 50
Marking multiples complete.

エラトステネスの篩のロジックを解説しましょう。

素数と非素数を追跡するためのブール型配列is_primeを作成します。
最初は、すべての数を素数としてマークします。
2 から sqrt(上限) までの数を反復処理します。
各素数に対して、その倍数を非素数としてマークします。
アルゴリズムを最適化するため、p^2 からマークを始めます。
内側のループは p だけ増やして p のすべての倍数をマークします。

すべての素数を表示する

このステップでは、与えられた範囲内で見つけたすべての素数を表示することで、エラトステネスの篩の実装を完了します。

表示機能を追加するためにprime_sieve.cファイルを修正しましょう。

cd ~/project
nano prime_sieve.c

素数を表示するようにコードを更新します。

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

int main() {
    int upper_limit;

    printf("Enter the upper limit for finding prime numbers: ");
    scanf("%d", &upper_limit);

    // 素数と非素数をマークするためのブール型配列を作成
    bool is_prime[upper_limit + 1];

    // すべての数を素数として初期化
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // 各素数の倍数を非素数としてマーク
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // p の倍数を非素数としてマーク
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    // すべての素数を表示
    printf("Prime numbers up to %d are:\n", upper_limit);
    for (int p = 2; p <= upper_limit; p++) {
        if (is_prime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");

    return 0;
}

プログラムをコンパイルして実行します。

gcc prime_sieve.c -o prime_sieve
./prime_sieve

出力例：

Enter the upper limit for finding prime numbers: 50
Prime numbers up to 50 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

最後の手順を解説しましょう。

倍数をマークした後、is_prime配列を反復処理します。
素数としてマークされたままの数だけを表示します。
出力には、ユーザーが指定した上限までのすべての素数が表示されます。

まとめ

この実験では、まず C 言語でエラトステネスの篩アルゴリズムの上限を読み取る方法を学びました。prime_sieve.cという C ファイルを作成し、ユーザーに上限を入力させ、それをupper_limit変数に格納するコードを書きました。次に、素数と非素数をマークするためのブール型配列を作成することで、エラトステネスの篩アルゴリズムの核心部分を実装しました。すべての数を素数として初期化し、次に各素数の倍数を非素数としてマークしました。最後に、与えられた上限内のすべての素数を表示する方法を学びました。

C 言語でエラトステネスの篩を実装する

はじめに

上限を読み取る

倍数を非素数としてマークする

すべての素数を表示する

まとめ