C 練習問題33 - 素数判定

C言語の定番100例

問題:ある数字が素数かどうかを判定する。

プログラム分析:素数(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

C言語の定番100例

その他の拡張