» 詳しい使用方法や、エラーで展開できない際の対応方法などはこちら
試し割り法による素数判定ツール
試し割り法により、数が素数かどうかを判定するVCSSLプログラムです。
スポンサーリンク
使用方法
ダウンロードと展開（解凍）
まず、PC（スマホは未対応）で上の画面の「 ダウンロード 」ボタンを押してください。 するとZIP形式で圧縮されたファイルがダウンロードされます。
その後、ZIPファイルを右クリックして「すべて展開」や「ここに展開」などで展開（解凍）してください。 展開が成功すると、ZIPファイルと同じ名前のフォルダができ、その中にZIPファイルの中身が入っています。
» 展開がエラーで止まってしまう場合や、ファイル名が文字化けしてしまう場合は…
プログラムの起動
Windows をご使用の場合
上記でZIPファイルを展開したフォルダ内にある、以下のバッチファイルをダブルクリック実行してください：
もしプログラムを書き変えながら使いたい場合は、代わりに「 VCSSL_Editor__プログラム編集はこちら.bat 」を実行してください。
正常に起動できると、初回のみ、Java実行環境を入手するか等を尋ねられるので、適時答えて済ませると、プログラムが起動します。 2回目以降はすぐに起動します。
Linux 等をご使用の場合
ZIPファイルを展開したフォルダ内へコマンドライン端末で cd して、以下の通り入力して実行してください：
（プログラムの内容を書き変えながら使いたい場合は、代わりに VCSSL_Editor.jar を実行）
» javaコマンドが使用できない等のエラーが表示される場合は…
操作方法
このプログラムを起動すると、数値の入力を要求するウィンドウが表示されますので、素数かどうかを判定したい整数を入力してください。すると、判定結果が表示されます。
題材解説
素数
このプログラムは、数が素数かどうかを判定するためのものです。素数とは、1以外の約数を持たない整数の事です。
最も単純な素数判定のアルゴリズム「 試し割り法 」
素数判定のアルゴリズムには、実に様々なものが存在します。例えば「エラトステネスのふるい」などは非常に有名ですね。
今回のプログラムでは、その中で最も単純な「 試し割り法 」を採用しています。 試し割り法は、素数の定義に基づいて、ひたすら約数を探していき（ 割って余りが 0 なら約数 ）、見つからなければ素数であると判断する方法です。 素数判定のアルゴリズムを考えた際、恐らく誰もが最初に思いつく方法なのではないでしょうか。
調べる約数の上限は √N で十分
ところで、素数の定義に忠実に考えるなら、判定対象の数を N として、2 以上 N 未満のすべての数について、N の約数とならない事を確かめなければいけない気がします。 しかし実際には、2 以上 √N 以下の数について調べれば十分です。
なぜなら、もし √N 以上の約数 A が存在すれば、残りの約数は N/A ( √N 以下 ) を分け合うので、残りの約数は √N 以下の範囲に存在するはずだからです。 1個でも約数があれば素数では無いと判定できるので、√N 以下を調べれば十分です。
有効桁数を考慮した安全マージン
しかしながら、VCSSLのint/long型(64bit)の桁数は20桁程度まで扱えるのに対し、 float/double型(64bit)の仮数部有効桁数は16桁程度なので、float/double型を扱う sqrt(N) を単純に上限にしてしまうと、 大きな数の判定ではやや精度に不安が残ります（ 引数にNを渡す時点で16桁程度に落ちてしまう ）。
そのため安全マージンを取って、sqrt( 1.5*N )を上限とします （ マージンを2*Nまで取ると、2の素数判定の場合に上限が2に一致してしまい、都合が悪い）。
コード解説
コーディング
ここまでで、素数と「試し割り法」アルゴリズムの解説は終わったので、ここからはそれをコーディングし、プログラムとして仕上げましょう。
まずは、コード全体をそのまま掲載します。
以上の通りです。それでは、細部を見ていきましょう。
ヘッダ領域の記述
まずは、プログラムの先頭、ヘッダ領域を記述しましょう。ここでは、文字コードの指定やライブラリのインポート、グローバル変数の宣言などを行います。
最初の行には、coding宣言を用いて文字コードを指定します。これは必須ではありませんが、指定しておくと文字化けによる不具合を防ぐ事ができます。使用可能な文字コードは「Shift_JIS」または「UTF-8」です。
続いてimport宣言で、必要なライブラリをインポートします。今回は、平方根を求めるsqrt関数を使うので、Mathライブラリをインポートします。
素数判定を行う isPrime 関数
まずは、コアとなる素数判定を行う関数を作りましょう。引数は判定対象の数をint型で受け取り、戻り値は判定結果をbool型で返すようにします。
- isPrime関数の仕様 -bool isPrime( int 判定する数 )
このisPrime関数は、例えば isPrime(7) は7が素数なのでtrueを返し、isPrime(8)は8が素数ではないのでfalseを返します。
それでは、isPrime関数の具体的な処理を実装しましょう。
- isPrime関数の実装 -* 素数判定を行う関数
* 引数nが素数ならtrueを、そうでなければfalseを返す
*/
bool isPrime( int n ){
int max = sqrt( 1.5*((double)n) ); // 約数を探す上限
// 素数は1より大きな自然数なので、1以下は素数でない
if( n <= 1 ){
return false;
}
// 2以上の数で約数が無いか探す
for( int i=2; i<=max; i++ ){
if( n % i == 0 ){
return false; // 割り切れれば、約数があるので素数でない
}
}
return true; // 割り切れなければ、約数が無いので素数
}
このように、まず変数 max に √(1.5*n) の値（ n でなく 1.5*n なのは、上述した通り安全マージン ）を求めておいて、2 以上 max 以下の範囲で約数が存在するか探しています。 i が約数かどうかは、n を i で割った余り（ n % i ）が0であるかどうかを調べる事で確認しています。
もし約数が見つかった場合は、その場で false を返し、関数の処理を抜けています。もしmaxまで探しても約数が無く、関数の最後に到達した場合は、素数なので true を返しています。
main 関数
別のプログラムと組み合わせて使用する場合は、上のisPrime関数だけで完成です。 関数のコードを別のプログラム中に直接貼り付けるなり、ファイルを置いて「 import PrimeTest; 」で読み込むなどして、isPrime関数を呼び出せば素数判定を行う事ができます。
しかしここでは、単体で実行しても使えるように、main関数を実装しておきましょう。ユーザーとやり取りして、整数を入力してもらい、素数判定結果を表示するようなものに仕上げます。
- main関数の実装 -/*
* main関数
* プログラムはここから開始される
*/
void main(){
// ユーザーが終了を希望するまで、処理をループ（繰り返し）する
bool loop = true; // ループ継続条件
while( loop ){
// ユーザーによる数値の入力
int number = input( "整数を入力してください - Please enter the number " );
// 素数判定と結果出力
if( isPrime( number ) ){
alert( number + " は素数です - is prime" );
}else{
alert( number + " は素数ではありません - is NOT prime" );
}
// ループの継続確認
loop = confirm( "別の数を判定しますか?" );
}
exit(); // ループを抜けたらプログラムを終了する
}
このように、input関数でユーザーに数を入力してもらい、それを if 文の条件式で素数かどうか判定し、結果で処理を分岐して、それぞれalert関数でメッセージを表示しています。ここの分岐判定で先ほどのisPrime関数を使用しています。
以上で、試し割り法による素数判定のプログラムは完成です。
ライセンス
このVCSSL/Vnanoコード（ 拡張子が「.vcssl」や「.vnano」のファイル ）は実質的な著作権フリー（パブリックドメイン) である CC0 の状態で公開しています※。 記事中にC言語/C++/Java言語などでのサンプルコードが掲載されいてる場合は、それらについても同様です。 そのままでのご利用はもちろん、改造や流用などもご自由に行ってください。
※ ただし、このコードの配布フォルダ内には、ダウンロード後すぐに実行できるように、 VCSSLの実行環境も同梱されており、そのライセンス文書は「 License 」フォルダ内に同梱されています （要約すると、商用・非商用問わず自由に使用できますが、使用の結果に対して開発元は一切の責任を負いません、といった具合の内容です）。 配布フォルダ内の各構成物の一覧やライセンスについては「 ReadMe_使用方法_必ずお読みください.txt 」をご参照ください。
※ Vnano の実行環境については、別途スクリプトエンジンのソースコードも一般公開しており、 何らかのソフトウェア内に組み込んでご利用いただく事も可能です。詳細はこちらをご参照ください。
この記事中の商標などについて
- OracleとJavaは、Oracle Corporation 及びその子会社、関連会社の米国及びその他の国における登録商標です。文中の社名、商品名等は各社の商標または登録商標である場合があります。
- Windows は、米国 Microsoft Corporation の米国およびその他の国における登録商標です。この記事は独立著作物であり、Microsoft Corporation と関連のある、もしくはスポンサーを受けるものではありません。
- Linux は、Linus Torvalds 氏の米国およびその他の国における商標または登録商標です。
- その他、文中に使用されている商標は、その商標を保持する各社の各国における商標または登録商標です。
|
角度の「度」とラジアンとを相互変換し、図示もするツール |
|
 |
45度などの「度」の値と、ラジアンの値とを相互に変換できるツールです。対応する角度の図示もできます。 |
|
FizzBuzz の答えを表示するプログラム |
|
 |
プログラミングの練習問題としても有名な、FizzBuzz 問題の答えを表示するプログラムの例です。 |
|
Vnano版 | 積分値のグラフ描画用データを出力するプログラム |
|
 |
数値的に積分を行い、結果の関数をグラフに描くためのデータを出力するコードです。 |
|
Vnano版 | 積分値を求めるプログラム (数値積分) |
|
 |
矩形法/台形法/シンプソン法を用いて、積分の値を数値的に求めるコードです。 |
|
入力された数式を積分して値とグラフを表示するツール |
|
 |
画面上で数式を入力すると、それを数値的に積分し、値とグラフを表示してくれるGUIツールです。 |
|
シンプソン法による数値積分 |
|
 |
積分の値を数値的に求めます。台形法よりも高精度な方法として、被積分関数を微小区間内で二次関数近似して求めた面積を足しあげる、シンプソン法を使用します。 |
|
台形法（台形近似）による数値積分 |
|
 |
積分の値を数値的に求めます。長方形近似よりも高精度な方法として、台形で近似した微小領域を足しあげる方法を使用します。 |
|
矩形法（長方形近似）による数値積分 |
|
 |
積分の値を数値的に求めます。長方形の短冊（矩形）で近似した微小領域を足しあげる、最も単純な方法を使用します。 |
|
小数（浮動小数点数）から分数へ近似的に変換するツール |
|
 |
小数（浮動小数点数）を、適当な誤差の範囲内で、近い分数に変換してくれるツールプログラムです。 |
|
円周率1万桁の計算（ガウス=ルジャンドル法） |
|
 |
ガウス=ルジャンドル法により、円周率を1万桁まで計算するプログラムです。 |
|
試し割り法による素数判定ツール |
|
 |
試し割り法を用いて、素数判定を行ってくれる簡易ツールです。 |
