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

この記事では、C言語を使って素数を判定する方法と列挙する方法を解説します。

目次から探す

素数の判定方法

方法1: 2から順番に割り切れるかどうかを調べる

素数を判定する方法の一つは、2から順番に値を割り切れるかどうかを調べる方法です。

具体的な手順は以下の通りです。

  1. 判定したい数値を変数に代入します。
  2. 2から始めて、変数の値より小さい数まで順番に割り算を行います。
  3. 割り算の結果、割り切れる数があれば、その数は素数ではありません。
  4. 割り切れる数がない場合、その数は素数です。

方法2: 2から√nまでの範囲で割り切れるかどうかを調べる

もう一つの素数の判定方法は、2から√nまでの範囲で割り切れるかどうかを調べる方法です。

具体的な手順は以下の通りです。

  1. 判定したい数値を変数に代入します。
  2. 2から√nまでの範囲で順番に割り算を行います。
  3. 割り算の結果、割り切れる数があれば、その数は素数ではありません。
  4. 割り切れる数がない場合、その数は素数です。

素数の列挙方法

方法1: 素数かどうかを判定しながら列挙する

素数を列挙する方法の一つは、素数かどうかを判定しながら順番に数を列挙する方法です。

具体的な手順は以下の通りです。

  1. 列挙したい素数の個数を指定します。
  2. 変数を用意し、2から始めます。
  3. 変数の値が素数であれば、その数を出力します。
  4. 素数である場合、列挙した素数の個数をカウントします。
  5. カウントした素数の個数が指定した個数に達するまで、変数の値をインクリメントしながら繰り返します。

方法2: エラトステネスの篩を使って列挙する

もう一つの素数の列挙方法は、エラトステネスの篩を使って素数を列挙する方法です。

具体的な手順は以下の通りです。

  1. 列挙したい素数の範囲を指定します。
  2. 範囲内の数を要素とする配列を用意します。
  3. 配列の要素を全て初期化します。
  4. 2から順番に数を取り出し、その数の倍数を篩い落とします。
  5. 篩い落とされなかった数は素数です。

サンプルコード

以下には、方法1と方法2の素数の判定と列挙のサンプルコードを示します。

#include <stdio.h>
// 素数の判定方法1: 2から順番に割り切れるかどうかを調べる
int isPrime1(int num) {
    if (num < 2) {
        return 0;
    }
    for (int i = 2; i < num; i++) {
        if (num % i == 0) {
            return 0;
        }
    }
    return 1;
}
// 素数の判定方法2: 2から√nまでの範囲で割り切れるかどうかを調べる
int isPrime2(int num) {
    if (num < 2) {
        return 0;
    }
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return 0;
        }
    }
    return 1;
}
// 素数の列挙方法1: 素数かどうかを判定しながら列挙する
void enumeratePrimes1(int count) {
    int num = 2;
    int primeCount = 0;
    while (primeCount < count) {
        if (isPrime1(num)) {
            printf("%d ", num);
            primeCount++;
        }
        num++;
    }
    printf("\n");
}
// 素数の列挙方法2: エラトステネスの篩を使って列挙する
void enumeratePrimes2(int range) {
    int primes[range + 1];
    for (int i = 0; i <= range; i++) {
        primes[i] = 1;
    }
    for (int i = 2; i * i <= range; i++) {
        if (primes[i]) {
            for (int j = i * i; j <= range; j += i) {
                primes[j] = 0;
            }
        }
    }
    for (int i = 2; i <= range; i++) {
        if (primes[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");
}
int main() {
    printf("方法1の素数判定結果: %d\n", isPrime1(17));
    printf("方法2の素数判定結果: %d\n", isPrime2(17));
    printf("方法1の素数列挙結果: ");
    enumeratePrimes1(10);
    printf("方法2の素数列挙結果: ");
    enumeratePrimes2(30);
    return 0;
}

上記のサンプルコードでは、方法1と方法2の素数の判定と列挙の関数を実装しています。

それぞれの関数を呼び出して、結果を表示しています。

目次から探す