はじめに

素数とは、1とその数自身以外の約数を持たない自然数です。例えば、2、3、5、7、11などが素数です。 C言語では、指定された範囲内の素数を列挙するプログラムを作成することができます。 この解説では、範囲内の素数を効率的に列挙する方法を紹介し、具体的なC言語のコードを通じてそのアルゴリズムを理解します。

素数判定アルゴリズム

素数を判定するためには、まずその数が1とその数自身以外の約数を持つかどうかをチェックする必要があります。 最も簡単な方法は、1からその数の平方根までの全ての整数で割り切れないかを確認することです。

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

int is_prime(int num) {
    if (num <= 1) {
        return 0; // 1以下は素数ではない
    }
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return 0; // 割り切れる場合は素数ではない
        }
    }
    return 1; // 割り切れない場合は素数
}
      
    

この関数は、指定された整数「num」が素数かどうかを判定します。最初に、numが1以下ならば素数ではないと返します。 次に、2からnumの平方根までの数で割り切れるかを確認し、割り切れれば素数ではないと判断します。 最後に、どの数でも割り切れなかった場合はその数が素数であると返します。

実行例

次に、指定された範囲内で素数を列挙するプログラムの例を示します。以下は、ユーザーが指定した範囲内で素数を表示するC言語のコードです。

      
#include <stdio.h>

int is_prime(int num);

int main() {
    int lower, upper;
    printf("素数を列挙する範囲を入力してください (例: 10 50): ");
    scanf("%d %d", &lower, &upper);

    printf("%d から %d までの素数は: \n", lower, upper);
    for (int i = lower; i <= upper; i++) {
        if (is_prime(i)) {
            printf("%d ", i);
        }
    }
    printf("\n");
    return 0;
}
      
    

このプログラムは、まずユーザーから範囲を入力してもらいます。その後、その範囲内のすべての数に対してis_prime関数を呼び出し、素数であれば表示します。 例えば、範囲が10から50の場合、以下のように出力されます：

      
素数を列挙する範囲を入力してください (例: 10 50): 10 50
10 から 50 までの素数は: 
11 13 17 19 23 29 31 37 41 43 47
      
    

まとめ

素数を列挙するプログラムは、素数判定アルゴリズムを理解するための良い練習になります。 素数判定は、数学的に効率的なアルゴリズムを使うことで、非常に高速に実行することができます。例えば、エラトステネスの篩（ふるい）を使うと、範囲内の素数をもっと効率的に列挙することができますが、今回紹介した方法でも十分に範囲を限定して素数を求めることができます。 このプログラムをベースに、範囲が大きくなる場合や、別の効率的なアルゴリズムを実装するなど、さらに発展させていくことができます。