この記事では、C言語を使って素数を判定する方法を解説します。
素数の判定方法
素数とは、1と自分自身以外の約数を持たない数のことです。
C言語を使って素数を判定する方法を解説します。
方法1: 2から順番に割り切れるか調べる
この方法では、2から順番に数を増やしながら、その数が他の数で割り切れるかどうかを調べます。
割り切れる数が存在した場合、その数は素数ではありません。
以下に、この方法を使った素数判定のサンプルコードを示します。
#include <stdio.h>
int isPrime(int num) {
if (num < 2) {
return 0;
}
for (int i = 2; i < num; i++) {
if (num % i == 0) {
return 0;
}
}
return 1;
}
int main() {
int n;
printf("整数を入力してください: ");
scanf("%d", &n);
if (isPrime(n)) {
printf("%dは素数です\n", n);
} else {
printf("%dは素数ではありません\n", n);
}
return 0;
}上記のコードでは、isPrime関数を定義しています。
この関数は、引数として与えられた数が素数かどうかを判定し、素数であれば1を、素数でなければ0を返します。
main関数では、ユーザーに整数を入力してもらい、その数が素数かどうかを判定して結果を表示しています。
方法2: 2から√nまでの範囲で割り切れるか調べる
この方法では、2から√nまでの範囲で数を増やしながら、その数が他の数で割り切れるかどうかを調べます。
√nまでの範囲で割り切れる数が存在した場合、その数は素数ではありません。
以下に、この方法を使った素数判定のサンプルコードを示します。
#include <stdio.h>
#include <math.h>
int isPrime(int num) {
if (num < 2) {
return 0;
}
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0) {
return 0;
}
}
return 1;
}
int main() {
int n;
printf("整数を入力してください: ");
scanf("%d", &n);
if (isPrime(n)) {
printf("%dは素数です\n", n);
} else {
printf("%dは素数ではありません\n", n);
}
return 0;
}上記のコードでは、isPrime関数を定義しています。
この関数は、引数として与えられた数が素数かどうかを判定し、素数であれば1を、素数でなければ0を返します。
main関数では、ユーザーに整数を入力してもらい、その数が素数かどうかを判定して結果を表示しています。
方法3: エラトステネスの篩を使う
エラトステネスの篩は、ある範囲内の数に対して素数を見つけるアルゴリズムです。
具体的な手順は以下の通りです。
- 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 p = 2; p <= n; p++) {
if (isPrime[p]) {
printf("%d ", p);
}
}
printf("\n");
}
int main() {
int n;
printf("整数を入力してください: ");
scanf("%d", &n);
sieveOfEratosthenes(n);
return 0;
}上記のコードでは、sieveOfEratosthenes関数を定義しています。
この関数は、引数として与えられた数までの素数を見つけて表示します。
main関数では、ユーザーに整数を入力してもらい、その数までの素数を見つけて表示しています。
以上が、C言語で素数を判定する方法の解説です。
