数値処理

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

2025-04-14更新日: 2025-04-14

C言語で素数を求める際、配列を活用することで効率的に計算を行うことができます。

エラトステネスの篩というアルゴリズムを使用すると、配列を用いて素数を効率的に判定できます。

この方法では、まず指定した範囲の整数を配列に格納し、2から始めてその倍数を配列から削除していきます。

最終的に配列に残った数が素数となります。

この手法は、特に大きな数の範囲で素数を求める際に有効です。

目次から探す

配列を使った素数の求め方
応用例
- 素数を使った暗号化
- 素数を使った数学的問題の解決
まとめ

配列を使った素数の求め方

素数とは何か

素数の定義

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

例えば、2, 3, 5, 7, 11などが素数です。

1は素数ではありません。

素数の性質

最小の素数は2: 2は唯一の偶数の素数です。
無限に存在する: 素数は無限に存在し、どんなに大きな数でも素数を見つけることができます。
整数の基本: 任意の整数は素数の積で表すことができます(素因数分解)。

配列の基本

配列の宣言と初期化

配列は同じ型のデータを連続して格納するためのデータ構造です。

C言語では、配列を次のように宣言し、初期化します。

#include <stdio.h>
int main() {
    // 配列の宣言と初期化
    int numbers[5] = {1, 2, 3, 4, 5};
    return 0;
}

配列の要素へのアクセス

配列の要素には、インデックスを使用してアクセスします。

インデックスは0から始まります。

#include <stdio.h>
int main() {
    int numbers[5] = {1, 2, 3, 4, 5};
    // 配列の要素へのアクセス
    printf("%d\n", numbers[0]); // 出力: 1
    return 0;
}

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

エラトステネスの篩

エラトステネスの篩は、古代ギリシャの数学者エラトステネスが考案した素数を求める効率的なアルゴリズムです。

以下の手順で素数を求めます。

2から始めて、数を順にチェックします。
現在の数が素数であれば、その倍数をすべてリストから削除します。
次の数に進み、リストが空になるまで繰り返します。

試し割り法

試し割り法は、ある数が素数かどうかを判定するために、その数の平方根までの素数で割り切れるかを確認する方法です。

割り切れる数がなければ、その数は素数です。

C言語での実装

エラトステネスの篩を使った実装

以下は、エラトステネスの篩を用いて素数を求めるC言語のサンプルコードです。

#include <stdio.h>
#include <stdbool.h>
#define MAX 100
int main() {
    bool isPrime[MAX];
    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;
            }
        }
    }
    for (int i = 2; i < MAX; i++) {
        if (isPrime[i]) {
            printf("%d ", i);
        }
    }
    return 0;
}

このプログラムは、0から99までの数の中で素数を判定し、素数を出力します。

isPrime配列を使って、各数が素数かどうかを管理しています。

試し割り法を使った実装

以下は、試し割り法を用いて素数を判定するC言語のサンプルコードです。

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
bool isPrime(int number) {
    if (number <= 1) return false;
    for (int i = 2; i <= sqrt(number); i++) {
        if (number % i == 0) return false;
    }
    return true;
}
int main() {
    for (int i = 2; i < 100; i++) {
        if (isPrime(i)) {
            printf("%d ", i);
        }
    }
    return 0;
}

このプログラムは、2から99までの数を試し割り法で素数判定し、素数を出力します。

isPrime関数で素数判定を行っています。

配列を使った素数の保存

配列に素数を格納する方法

素数を配列に格納するには、素数判定を行い、素数であると判定された数を配列に追加します。

以下はその例です。

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#define MAX 100
#define PRIME_COUNT 25 // 100以下の素数の数
bool isPrime(int number) {
    if (number <= 1) return false;
    for (int i = 2; i <= sqrt(number); i++) {
        if (number % i == 0) return false;
    }
    return true;
}
int main() {
    int primes[PRIME_COUNT];
    int index = 0;
    for (int i = 2; i < MAX; i++) {
        if (isPrime(i)) {
            primes[index++] = i;
        }
    }
    for (int i = 0; i < index; i++) {
        printf("%d ", primes[i]);
    }
    return 0;
}