この記事では、C言語を使って素数を判定する方法と列挙する方法を解説します。
目次から探す
素数の判定方法
方法1: 2から順番に割り切れるかどうかを調べる
素数を判定する方法の一つは、2から順番に値を割り切れるかどうかを調べる方法です。
具体的な手順は以下の通りです。
- 判定したい数値を変数に代入します。
- 2から始めて、変数の値より小さい数まで順番に割り算を行います。
- 割り算の結果、割り切れる数があれば、その数は素数ではありません。
- 割り切れる数がない場合、その数は素数です。
方法2: 2から√nまでの範囲で割り切れるかどうかを調べる
もう一つの素数の判定方法は、2から√nまでの範囲で割り切れるかどうかを調べる方法です。
具体的な手順は以下の通りです。
- 判定したい数値を変数に代入します。
- 2から√nまでの範囲で順番に割り算を行います。
- 割り算の結果、割り切れる数があれば、その数は素数ではありません。
- 割り切れる数がない場合、その数は素数です。
素数の列挙方法
方法1: 素数かどうかを判定しながら列挙する
素数を列挙する方法の一つは、素数かどうかを判定しながら順番に数を列挙する方法です。
具体的な手順は以下の通りです。
- 列挙したい素数の個数を指定します。
- 変数を用意し、2から始めます。
- 変数の値が素数であれば、その数を出力します。
- 素数である場合、列挙した素数の個数をカウントします。
- カウントした素数の個数が指定した個数に達するまで、変数の値をインクリメントしながら繰り返します。
方法2: エラトステネスの篩を使って列挙する
もう一つの素数の列挙方法は、エラトステネスの篩を使って素数を列挙する方法です。
具体的な手順は以下の通りです。
- 列挙したい素数の範囲を指定します。
- 範囲内の数を要素とする配列を用意します。
- 配列の要素を全て初期化します。
- 2から順番に数を取り出し、その数の倍数を篩い落とします。
- 篩い落とされなかった数は素数です。
サンプルコード
以下には、方法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の素数の判定と列挙の関数を実装しています。
それぞれの関数を呼び出して、結果を表示しています。