C 練習問題33 - 素数判定
問題:ある数字が素数かどうかを判定する。
プログラム分析:素数(prime number)は無限に存在する。1より大きい自然数で、1とそれ自身以外の自然数では割り切れない数である。
プログラムのソースコード:
実例
#include<stdio.h>
#include<math.h>
#define MAX 1000 // 最大配列サイズ
int prime[MAX]; // 素数かどうかを格納する配列
// 数字が素数かどうかを判定する簡単な方法(ブルートフォース法)
int isPrimeNaive(int n)
{
if (n <= 1) // 1以下の数字は素数ではない
return 0;
for (int i = 2; i < n; i++) // 2からn-1まで順にnを割り切れるか確認する
if (n % i == 0) // 割り切れれば素数ではない
return 0;
return 1; // 因数が見つからなければ素数である
}
// 最適化した素数判定方法:sqrt(n)まで調べ、偶数をスキップする
int isPrime(int n)
{
if (n <= 1) // 1以下の数字は素数ではない
return 0;
if (n == 2) // 2は素数である
return 1;
if (n % 2 == 0) // 偶数を除外する
return 0;
int limit = (int)sqrt((double)n); // sqrt(n)まで調べるだけでよい
for (int i = 3; i <= limit; i += 2) // 3から始めて奇数のみ調べる
{
if (n % i == 0) // 割り切れれば素数ではない
return 0;
}
return 1; // すべてのテストを通過すれば、nは素数である
}
// 篩法で素数表を初期化する
void sieve()
{
for (int i = 0; i < MAX; i++)
prime[i] = 1; // すべての数が素数であると仮定する
prime[0] = prime[1] = 0; // 0と1は素数ではない
int limit = (int)sqrt((double)MAX); // sqrt(MAX)まで調べるだけでよい
for (int i = 2; i <= limit; i++) // 2から始めて各数字を走査する
{
if (prime[i]) // iが素数なら
{
for (int j = i * i; j < MAX; j += i) // iの倍数を非素数としてマークする
prime[j] = 0;
}
}
}
// 篩法で数が素数かどうかを判定する
int isPrimeSieve(int n)
{
return prime[n]; // その位置が素数かどうかを直接返す
}
int main()
{
sieve(); // 素数篩を初期化する
// 様々な数字が素数かどうかをテストする
printf("N=%d %d\n", 1, isPrime(1)); // 出力:1 は素数ではない
printf("N=%d %d\n", 2, isPrime(2)); // 出力:2 は素数である
printf("N=%d %d\n", 3, isPrime(3)); // 出力:3 は素数である
printf("N=%d %d\n", 4, isPrime(4)); // 出力:4 は素数ではない
printf("N=%d %d\n", 7, isPrime(7)); // 出力:7 は素数である
printf("N=%d %d\n", 9, isPrime(9)); // 出力:9 は素数ではない
printf("N=%d %d\n", 13, isPrime(13)); // 出力:13 は素数である
printf("N=%d %d\n", 17, isPrime(17)); // 出力:17 は素数である
printf("N=%d %d\n", 100, isPrime(100)); // 出力:100 は素数ではない
printf("N=%d %d\n", 23, isPrime(23)); // 出力:23 は素数である
printf("N=%d %d\n", 1, isPrime(1)); // 出力:1 は素数ではない
return 0;
}
上記の実例の出力結果は次の通りです(末尾の数字 1 は素数、0 は素数でないことを示します):
N=1 0 N=2 1 N=3 1 N=4 0 N=7 1 N=9 0 N=13 1 N=17 1 N=100 0 N=23 1 N=1 0その他の拡張