この記事では、C言語を使って素数を判定するプログラムを作成する方法を解説します。
目次から探す
素数の判定方法
素数の定義と特徴
素数とは、1と自分自身以外の約数を持たない自然数のことです。
例えば、2や3、5、7などが素数です。
素数には以下のような特徴があります。
- 素数は必ず奇数です(2を除く)。
- 素数は他の数で割り切れないため、約数の個数は2つです。
素数の判定方法のアルゴリズム
素数を判定する方法にはいくつかのアルゴリズムがありますが、ここでは「試し割り法」を紹介します。
試し割り法は、2から順番に割り算をしていき、割り切れる数があるかどうかを調べる方法です。
具体的な手順は以下の通りです。
- 判定したい数をnとする。
- 2からn-1までの数でnを割り算する。
- 割り切れる数があれば、nは素数ではない。
- 割り切れる数がなければ、nは素数である。
プログラムの実装
プログラムの基本的な構造
素数を求めるプログラムの基本的な構造は以下の通りです。
- 素数を格納するための配列を用意する。
- 素数を判定する関数を作成する。
- 2から順番に数を判定し、素数であれば配列に格納する。
- 指定した個数の素数が格納されたら、プログラムを終了する。
プログラムの各部分の実装方法
- 素数を格納するための配列を用意する。
#define MAX_PRIMES 100
int primes[MAX_PRIMES];
- 素数を判定する関数を作成する。
int isPrime(int n) {
if (n <= 1) {
return 0;
}
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}
- 2から順番に数を判定し、素数であれば配列に格納する。
int count = 0;
int num = 2;
while (count < MAX_PRIMES) {
if (isPrime(num)) {
primes[count] = num;
count++;
}
num++;
}
- 指定した個数の素数が格納されたら、プログラムを終了する。
for (int i = 0; i < MAX_PRIMES; i++) {
printf("%d ", primes[i]);
}
このプログラムは、100個の素数を求める例です。
必要に応じて、MAX_PRIMESの値を変更してください。