この記事では、C言語を使って素数を表示するプログラムの作り方を解説します。
まず、素朴な方法で素数を見つける基本的なプログラムを紹介し、その後、より効率的なエラトステネスの篩(ふるい)という方法を使ったプログラムを説明します。
初心者の方でも理解しやすいように、サンプルコードと実行結果を交えて丁寧に解説していきますので、ぜひ最後まで読んでみてください。
素朴な方法で素数を表示するプログラム
素数を表示するプログラムを作成するための最も基本的な方法は、素朴な方法(Brute Force)です。
この方法では、各数値が素数かどうかを一つ一つ確認していきます。
以下に、素朴な方法で素数を表示するプログラムの実装手順を解説します。
素朴な方法の実装
ループの設定
まず、素数を判定するために、ある範囲内の数値を順にチェックするループを設定します。
例えば、1から100までの数値をチェックする場合、以下のようにループを設定します。
for (int i = 2; i <= 100; i++) {
// 素数判定の処理
}素数判定の条件
次に、各数値が素数かどうかを判定する条件を設定します。
素数とは、1とその数自身以外に約数を持たない数のことです。
したがって、2からその数の平方根までの数で割り切れるかどうかをチェックします。
int is_prime = 1; // 素数であると仮定
for (int j = 2; j * j <= i; j++) {
if (i % j == 0) {
is_prime = 0; // 素数ではない
break;
}
}素数の表示
素数であると判定された数値を表示します。
素数であるかどうかのフラグ(is_prime)が1のままであれば、その数は素数です。
if (is_prime) {
printf("%d ", i);
}プログラムの全体像
以上の手順を組み合わせると、素朴な方法で素数を表示するプログラムの全体像は以下のようになります。
#include <stdio.h>
int main() {
for (int i = 2; i <= 100; i++) {
int is_prime = 1; // 素数であると仮定
for (int j = 2; j * j <= i; j++) {
if (i % j == 0) {
is_prime = 0; // 素数ではない
break;
}
}
if (is_prime) {
printf("%d ", i);
}
}
return 0;
}実行結果の例
上記のプログラムを実行すると、1から100までの素数が表示されます。
実行結果の例は以下の通りです。
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97このように、素朴な方法を用いることで、簡単に素数を表示するプログラムを作成することができます。
ただし、この方法は効率が悪いため、大きな範囲の素数を求める場合には他の方法(例えばエラトステネスの篩)を検討する必要があります。
エラトステネスの篩を使った素数表示プログラム
エラトステネスの篩(ふるい)は、古代ギリシャの数学者エラトステネスが考案した素数を効率的に見つけるためのアルゴリズムです。
この方法を使うと、素数を効率的に求めることができます。
ここでは、エラトステネスの篩を使った素数表示プログラムの実装方法を解説します。
エラトステネスの篩の実装
エラトステネスの篩の実装は以下の手順で行います。
配列の初期化
まず、素数かどうかを判定するための配列を用意します。
この配列の各要素は、対応する数が素数であるかどうかを示します。
初期状態では、すべての数を素数と仮定します。
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
int main() {
bool isPrime[MAX + 1];
for (int i = 0; i <= MAX; i++) {
isPrime[i] = true; // 初期状態ではすべての数を素数と仮定
}篩の処理
次に、2から始めて、各数が素数かどうかを判定し、素数であればその倍数をすべて素数ではないとマークします。
この処理を配列の最後まで繰り返します。
for (int p = 2; p * p <= MAX; p++) {
if (isPrime[p]) {
for (int i = p * p; i <= MAX; i += p) {
isPrime[i] = false; // 素数の倍数を素数ではないとマーク
}
}
}素数の表示
最後に、配列の中で素数とマークされている数を表示します。
printf("素数: ");
for (int p = 2; p <= MAX; p++) {
if (isPrime[p]) {
printf("%d ", p);
}
}
printf("\n");
return 0;
}プログラムの全体像
上記の手順をまとめると、以下のようなプログラムになります。
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
int main() {
bool isPrime[MAX + 1];
for (int i = 0; i <= MAX; i++) {
isPrime[i] = true; // 初期状態ではすべての数を素数と仮定
}
for (int p = 2; p * p <= MAX; p++) {
if (isPrime[p]) {
for (int i = p * p; i <= MAX; i += p) {
isPrime[i] = false; // 素数の倍数を素数ではないとマーク
}
}
}
printf("素数: ");
for (int p = 2; p <= MAX; p++) {
if (isPrime[p]) {
printf("%d ", p);
}
}
printf("\n");
return 0;
}実行結果の例
このプログラムを実行すると、以下のように素数が表示されます。
素数: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97このように、エラトステネスの篩を使うことで、効率的に素数を求めることができます。
篩の処理を理解することで、より高度なアルゴリズムの理解にもつながります。
