この記事では、C言語で数値が素数かどうかを判定する方法を解説します。
目次から探す
C言語での素数判定の実装方法
素数判定は、与えられた数値が素数であるかどうかを判定する処理です。
C言語では、いくつかの方法を使って素数判定を行うことができます。
以下では、代表的な2つの方法、ブルートフォース法とエラトステネスの篩について解説します。
ブルートフォース法の実装
ブルートフォース法は、与えられた数値を2からその数値の平方根までの範囲で割り算を行い、割り切れる数が存在するかどうかを調べる方法です。
割り切れる数が存在しなければ、その数値は素数と判定されます。
以下に、ブルートフォース法を用いた素数判定の実装例を示します。
#include <stdio.h>
int isPrime(int num) {
if (num <= 1) {
return 0; // 1以下の数は素数ではない
}
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return 0; // 割り切れる数が存在するため、素数ではない
}
}
return 1; // 割り切れる数が存在しないため、素数である
}
int main() {
int num;
printf("数値を入力してください: ");
scanf("%d", &num);
if (isPrime(num)) {
printf("%dは素数です\n", num);
} else {
printf("%dは素数ではありません\n", num);
}
return 0;
}上記のコードでは、isPrime関数を定義しています。
この関数は、引数として与えられた数値が素数であるかどうかを判定し、結果を返します。
main関数では、ユーザーから数値を入力し、isPrime関数を呼び出して結果を表示しています。
エラトステネスの篩の実装
エラトステネスの篩は、ある範囲内の数値から素数を見つけるための効率的なアルゴリズムです。
具体的な手順は以下の通りです。
- 2から始まる連続した数列を用意する。
- 2の倍数を除外する。
- 残った数列の中で最小の数を素数として確定する。
- 素数の倍数を除外する。
- 3から繰り返し、素数を確定していく。
以下に、エラトステネスの篩を用いた素数判定の実装例を示します。
#include <stdio.h>
#include <stdbool.h>
void sieveOfEratosthenes(int n) {
bool isPrime[n+1];
for (int i = 0; i <= n; i++) {
isPrime[i] = true;
}
for (int p = 2; p * p <= n; p++) {
if (isPrime[p] == true) {
for (int i = p * p; i <= n; i += p) {
isPrime[i] = false;
}
}
}
printf("2から%dまでの素数: ", n);
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
printf("%d ", i);
}
}
printf("\n");
}
int main() {
int num;
printf("数値を入力してください: ");
scanf("%d", &num);
sieveOfEratosthenes(num);
return 0;
}上記のコードでは、sieveOfEratosthenes関数を定義しています。
この関数は、引数として与えられた数値までの素数を見つけて表示します。
main関数では、ユーザーから数値を入力し、sieveOfEratosthenes関数を呼び出して結果を表示しています。
以上が、C言語での素数判定の実装方法についての解説です。
ブルートフォース法とエラトステネスの篩の2つの方法を紹介しました。