この記事では、C言語を使って素数を求める方法と、素数を1000個求めるプログラムの書き方を紹介します。
目次から探す
素数の求め方
素数とは、1と自分自身以外の約数を持たない正の整数のことです。
素数を求める方法にはいくつかのアルゴリズムがありますが、ここでは「ブルートフォース法」と「エラトステネスの篩」について説明します。
方法1: ブルートフォース法
ブルートフォース法は、ある数が素数かどうかを判定するために、その数を2から順番に割っていき、割り切れる数が存在するかどうかを調べる方法です。
具体的な手順は以下の通りです。
- 判定したい数をnとする。
- nを2からn-1までの数で順番に割っていき、割り切れる数が存在するかどうかを調べる。
- 割り切れる数が存在しない場合、nは素数であると判定する。
この方法は非常に単純な方法ですが、大きな数に対しては効率が悪いため、計算時間がかかる可能性があります。
方法2: エラトステネスの篩
エラトステネスの篩は、ある範囲内の数から素数を見つけるための効率的な方法です。
具体的な手順は以下の通りです。
- 範囲内の数を表す配列を用意する。
初期値は全て「素数である」とする。
- 2から順番に数を取り出し、その数が素数である場合、その数の倍数を全て「素数ではない」とする。
- 繰り返し処理を行い、範囲内の数を順番に取り出して素数を見つける。
この方法は、範囲内の数を一度に判定するため、ブルートフォース法よりも効率的に素数を見つけることができます。
プログラムの実装
ブルートフォース法を用いた実装
#include <stdio.h>
int main() {
int count = 0; // 素数の個数をカウントする変数
int num = 2; // 判定する数の初期値
while (count < 1000) {
int isPrime = 1; // 素数かどうかを判定するフラグ
for (int i = 2; i <= num / 2; i++) {
if (num % i == 0) {
isPrime = 0; // 割り切れる数が存在する場合、素数ではない
break;
}
}
if (isPrime) {
printf("%d ", num);
count++;
}
num++;
}
return 0;
}上記のプログラムは、ブルートフォース法を用いて1000個の素数を求めるものです。
変数countを用いて素数の個数をカウントし、変数numを2から順番に増やしていきます。
内部のforループでは、numを2からnum/2までの数で割っていき、割り切れる数が存在するかどうかを調べます。
割り切れる数が存在しない場合、isPrimeを1に設定し、素数として出力します。
エラトステネスの篩を用いた実装
#include <stdio.h>
int main() {
int count = 0; // 素数の個数をカウントする変数
int primes[1000]; // 素数を格納する配列
// 初期化
for (int i = 0; i < 1000; i++) {
primes[i] = 1; // 全ての数を素数として初期化
}
for (int i = 2; count < 1000; i++) {
if (primes[i]) {
printf("%d ", i);
count++;
// iの倍数を全て素数ではないとする
for (int j = i * 2; j < 1000; j += i) {
primes[j] = 0;
}
}
}
return 0;
}上記のプログラムは、エラトステネスの篩を用いて1000個の素数を求めるものです。
配列primesを用意し、初期値を全て1(素数)とします。
外部のforループでは、2から順番に数を取り出し、その数が素数である場合に出力します。
また、その数の倍数を全て素数ではないとして配列primesの該当する要素を0に設定します。