【C言語】for文を使った素数の判定
素数とは
素数は、1とその数自身以外には約数を持たない、1より大きい自然数のことです。例えば、2, 3, 5, 7, 11 などが素数です。
素数を判定するには、ある数がそれ自身と1以外の数で割り切れるかどうかを調べる必要があります。例えば、17は素数ですが、18は素数ではありません。
素数判定アルゴリズム
素数を判定するための基本的なアルゴリズムは以下の手順です：
- 判定したい数が2より小さい場合、それは素数ではないとする。
- 数を1からその数の平方根までの数で割り切れるかどうかをチェックする。
- 割り切れる数があれば、その数は素数ではない。
- すべての割り算で割り切れなければ、その数は素数である。
for文を使った実装方法
C言語でfor文を使って素数判定を行う方法を紹介します。まず、判定したい数が2以上であるかを確認し、次にその数を1からその数の平方根までの数で割り切れるかをチェックします。
#include <stdio.h>
#include <math.h>
int is_prime(int num) {
if (num <= 1) return 0; // 1以下は素数でない
if (num == 2) return 1; // 2は素数
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0) {
return 0; // 割り切れる数があれば素数ではない
}
}
return 1; // 割り切れる数がなければ素数
}
int main() {
int num = 29;
if (is_prime(num)) {
printf("%dは素数です。\n", num);
} else {
printf("%dは素数ではありません。\n", num);
}
return 0;
}
上記のプログラムでは、is_prime関数を使って与えられた数が素数かどうかを判定します。for文で2からその数の平方根まで割り算を行い、割り切れる数があれば素数ではないと判断します。
例1: 10までの素数を求めるプログラム
次に、10までの素数を求める例を示します。
#include <stdio.h>
#include <math.h>
int is_prime(int num) {
if (num <= 1) return 0;
if (num == 2) return 1;
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0) {
return 0;
}
}
return 1;
}
int main() {
printf("10までの素数: ");
for (int i = 2; i <= 10; i++) {
if (is_prime(i)) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}
上記のプログラムでは、2から10までの数をfor文でチェックし、素数であれば表示します。実行結果は「2 3 5 7」となります。
効率化: 判定範囲を減らす
素数判定を効率化するためには、いくつかの最適化が可能です。例えば、以下のような方法があります：
- 2以降の偶数はすべて素数ではないため、偶数のチェックを省略できます。
- 平方根までのチェックを行うことで、無駄な計算を減らします。
これらの最適化を反映したプログラムは以下の通りです：
#include <stdio.h>
#include <math.h>
int is_prime(int num) {
if (num <= 1) return 0;
if (num == 2) return 1; // 2は素数
if (num % 2 == 0) return 0; // 偶数は素数ではない
for (int i = 3; i <= sqrt(num); i += 2) {
if (num % i == 0) {
return 0;
}
}
return 1;
}
int main() {
printf("10までの素数: ");
for (int i = 2; i <= 10; i++) {
if (is_prime(i)) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}
この最適化により、無駄な計算が減り、プログラムが高速に動作します。
高度な実装例
さらに効率的な素数判定方法として、エラトステネスの篩（ふるい）を使った方法があります。これは、1からnまでのすべての数を素数かどうか判定するために、複数の数を一度に扱う方法です。
エラトステネスの篩を使った実装は、特に大きな範囲で素数を求めるときに非常に有効です。以下はその基本的な実装方法です：
#include <stdio.h>
void sieve_of_eratosthenes(int n) {
int sieve[n+1];
for (int i = 0; i <= n; i++) {
sieve[i] = 1; // 全ての数を素数としてマーク
}
sieve[0] = sieve[1] = 0; // 0と1は素数ではない
for (int i = 2; i * i <= n; i++) {
if (sieve[i] == 1) {
for (int j = i * i; j <= n; j += i) {
sieve[j] = 0; // 素数でない数をマーク
}
}
}
printf("素数: ");
for (int i = 2; i <= n; i++) {
if (sieve[i] == 1) {
printf("%d ", i);
}
}
printf("\n");
}
int main() {
int n = 30;
sieve_of_eratosthenes(n);
return 0;
}
この方法では、2からnまでの数について素数判定を一度に行うことができ、効率的です。