素数とは,自明な正の約数(1 と自分自身)以外に約数を持たない自然数であり,1 でない数のことです.
ここでは,素数に関連するプログラムのサンプルを幾つか紹介します.
与ええられた数 n が素数であるか合成数であるかを判定するためのアルゴリズムは多数考案されていますが,サンプルプログラムでは最も素朴な方法である 2 から √n 以下の素数まで順番に割っていく方法を採ります. その他の素数判定法や素因数分解法の詳細は,素数 を参照してください.
指定された数が素数か否かと判定するプログラムです.ソースプログラムは,prime.c です.
プログラムはコマンドとして起動するもので,仕様は以下です.
prime num パラメータ: num: 判定対象数
num は int 型の範囲です.
指定された数を素因数分解するプログラムです.ソースプログラムは,pfactors.c です.
プログラムはコマンドとして起動するもので,仕様は以下です.
pfactors num パラメータ: num: 素因数分解の対象数
指定された数を素因数分解して表示します(num は int 型の範囲です).
"エラトステネスの篩"を用いて素数のリストを生成するプログラムです.ソースプログラムは,primelist.c です.
プログラムはコマンドとして起動するもので,仕様は以下です.
primelist [num] パラメータ: num: 最大数 (省略時: 10000)
指定された数 num 以下の素数を全て表示します(num は int 型の範囲です).また,その時の素数の数を表示します.