素数判定方法、素数判定装置および素数判定プログラム
【課題】 所定の範囲の既知の素数のみに基づき、大きな対象数についても判定可能な素数判定方法、素数判定装置および素数判定プログラムを提供する。
【解決手段】 対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定方法であって、対象数Ｎの入力を受け付ける入力受付過程と、対象数Ｎを除する除数の範囲を定める範囲規定過程と、対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定過程と、対象数Ｎが素数であるか否かの結果を出力する結果出力過程と、を備え、範囲規定過程は、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとして、Ｎ1/2／ＭＰの小数点以下を切り上げた規定数Ｒを算出するものであり、素数判定過程は、整数を１からＭＰ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭＰを構成する素数を除いた素数列の数を除数とする。
【解決手段】 対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定方法であって、対象数Ｎの入力を受け付ける入力受付過程と、対象数Ｎを除する除数の範囲を定める範囲規定過程と、対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定過程と、対象数Ｎが素数であるか否かの結果を出力する結果出力過程と、を備え、範囲規定過程は、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとして、Ｎ1/2／ＭＰの小数点以下を切り上げた規定数Ｒを算出するものであり、素数判定過程は、整数を１からＭＰ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭＰを構成する素数を除いた素数列の数を除数とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、対象数が素数であるか否かを判定する素数判定方法、素数判定装置および素数判定プログラムに関する。
【背景技術】
【０００２】
ある正の整数（対象数Ｎ）が素数であるか否かを判定する方法として最も単純なものは、Ｎを２以上Ｎ未満の整数で順次割り算し、割り切れる整数がなければ素数、一つでも割り切れる整数があれば非素数とするものである。しかし、この方法は計算量が非常に多くなるため、従来、もっと少ない計算量で素数判定を行うための種々の方法が提案されている。たとえば、古くから周知の方法として「エラトステネスのふるい」があり、この方法は、対象数Ｎについて、Ｎの平方根Ｎ1/2以下のすべての素数で割り切れなければＮを素数とするものである。また近年では、素数判定はコンピュータシステムにおける暗号技術とも深く関係している。たとえば特許文献１において、対象数Ｎの平方根Ｎ1/2以下の全ての素数が予め記憶されている素数記憶手段と、素数記憶手段内の何れの素数でも割り切れない正の整数αが予め記憶されている整数記憶手段とを用い、対象数Ｎと整数αとを乗算し（乗算結果ｍ＝Ｎα）、乗算結果ｍを素数記憶手段内の何れかの素数で割り算して余りｒを算出し、余りｒが素数記憶手段の何れの素数で割った場合も０でないとき、対象数Ｎを素数であると判定する素数判定方法が提案されており、これにより、素数判定時に電力解析やタイミング解析を施されても、素数候補の漏洩を阻止できる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００２−２６８５４８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、「エラトステネスのふるい」や文献１の方法は、いずれも対象数Ｎの平方根Ｎ1/2以下の素数が既知であることを前提とし、予め用意された素数のリストを参照するものであり、対象数Ｎが大きくなると必要な素数のリストも大きくなること、逆に言えば、既知の素数の最大値の二乗の数までしか対象にできないことが問題であった。
【０００５】
本発明は、上記事情を鑑みたものであり、所定の範囲の既知の素数のみに基づき、大きな対象数についても判定可能な素数判定方法、素数判定装置および素数判定プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のうち請求項１の発明は、対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定方法であって、入力受付手段が、対象数Ｎの入力を受け付ける入力受付過程と、範囲規定手段が、対象数Ｎを除する除数の範囲を定める範囲規定過程と、素数判定手段が、対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定過程と、結果出力手段が、対象数Ｎが素数であるか否かの結果を出力する結果出力過程と、を備え、前記範囲規定過程は、範囲規定手段が、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとして、Ｎ1/2／ＭＰの小数点以下を切り上げた規定数Ｒを算出するものであり、前記素数判定過程は、素数判定手段が、整数を１からＭＰ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭＰを構成する素数を除いた素数列の数を除数とするものであることを特徴とする。
【０００７】
本発明のうち請求項２の発明は、対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定装置であって、対象数Ｎの入力を受け付ける入力受付手段と、対象数Ｎを除する除数の範囲を定める範囲規定手段と、対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定手段と、対象数Ｎが素数であるか否かの結果を出力する結果出力手段と、を備え、前記範囲規定手段が、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとして、Ｎ1/2／ＭＰの小数点以下を切り上げた規定数Ｒを算出するものであり、前記素数判定手段が、整数を１からＭＰ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭＰを構成する素数を除いた素数列の数を除数とするものであることを特徴とする。
【０００８】
本発明のうち請求項３の発明は、対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定プログラムであって、対象数Ｎの入力を受け付ける入力受付ステップと、対象数Ｎを除する除数の範囲を定める範囲規定ステップと、対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定ステップと、対象数Ｎが素数であるか否かの結果を出力する結果出力ステップと、をコンピュータに実行させるためのものであって、前記範囲規定ステップが、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとして、Ｎ1/2／ＭＰの小数点以下を切り上げた規定数Ｒを算出するものであり、前記素数判定ステップが、整数を１からＭＰ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭＰを構成する素数を除いた素数列の数を除数とするものであることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、配列の第１行の素数、すなわちＭＰ以下の素数さえ予め把握されていれば、対象数Ｎがどれだけ大きくなっても、それ以上除数としての素数を算出する必要がない。よって、巨大な整数についても、コンピュータの性能に制限されることなく、容易に素数判定を行うことができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の素数判定プログラムの処理の流れを示すフローチャート。
【発明を実施するための形態】
【００１１】
以下、本発明の素数判定方法について、具体的に説明する。この素数判定方法は、正の整数である対象数Ｎに対して除数を定め、何れかの除数で割り切れた場合には非素数と判定し、何れの除数でも割り切れない場合には素数と判定するものであり、除数の規定方法に特徴がある。そこで、まず除数の規定方法の前提となる考え方について説明する。
【００１２】
まず、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとする。たとえば、Ｍ２＝２×３＝６、Ｍ３＝２×３×５＝３０、Ｍ４＝２×３×５×７＝２１０である。
【００１３】
次に、整数を１からＭＰ列に並べた配列を考える。以下の表１に示すのは、Ｍ２＝６の場合である。ここで、配列中の素数（白抜き文字で表示）の位置に注目すると、最初の二つの素数（２，３）以外の素数は、第１列および第５列に現れることがわかる。
【００１４】
【表１】
【００１５】
同様に、以下の表２に示すのは、Ｍ３＝３０の場合である。ここで、配列中の素数の位置に注目すると、最初の三つの素数（２，３，５）以外の素数は、第１列、第７列、第１１列、第１３列、第１７列、第１９列、第２３列、第２９列に現れることがわかる。
【００１６】
【表２】
【００１７】
すなわち、整数を１からＭＰ列に並べた配列において、素数は、第１行に現れる最初のＰ個の素数を除いて、第１列および最初のＰ個の素数を除いた素数列に現れ、それ以外の列には現れない。以下、第１列および最初のＰ個の素数を除いた素数列を、出現列とよぶ。
【００１８】
ここで、「エラトステネスのふるい」によれば、対象数Ｎについて、Ｎの平方根Ｎ1/2以下のすべての素数で割り切れなければＮを素数と判定できるが、そのためには、除数としてＮ1/2以下のすべての素数が予め把握されていなければならなかった。しかし、上記の配列を考えると、出現列にはすべての素数（最初のＰ個を除く）が含まれている。よって、対象数Ｎに対して、Ｎ1/2／ＭＰの小数点以下を切り上げた数を規定数Ｒとして、除数を、第１行の素数および第２行から第Ｒ行の出現列の数とすれば、その中にはＮ1/2以下のすべての素数が含まれていることになるので、素数判定を行うことができる。その際、配列のＡ行Ｂ列の値Ｘは、Ｘ＝Ｂ＋ＭＰ×（Ａ−１）で与えられるので、容易に求めることができる。なお、出現列には非素数も含まれているが、それらは必ずその数より小さい素数の倍数となっているから、素数判定に影響はない。
【００１９】
このように、本発明の素数判定方法によれば、対象数Ｎがどれだけ大きくなっても、配列の第１行の素数、すなわちＭＰ以下の素数さえ予め把握されていれば、それ以上の除数を求めることは容易であり、従来の方法のように、除数としての素数を算出する必要がない。よって、巨大な整数についても、コンピュータの性能に制限されることなく、容易に素数判定を行うことができる。
【００２０】
実際に本発明の素数判定方法を実施するには、以下に示す素数判定装置および素数判定プログラムを利用する。なお、ここではＰ＝３（Ｍ３＝３０）とした場合の例を示す。
【００２１】
本発明の素数判定プログラムは、キーボードやマウスなどからなる入力装置、ディスプレイなどからなる出力装置、本プログラムの命令を順番に実行するＣＰＵ、本プログラム、本プログラムの実行に必要なデータおよび判定結果などを保存しておく記憶装置を構成要素とする標準的なコンピュータにより実行される。また、本発明の素数判定装置は、前記プログラムが実行されるコンピュータにより構成される。
【００２２】
本プログラムをコンピュータに実行させた場合、コンピュータが各種の手段（入力受付手段、範囲規定手段、素数判定手段、結果出力手段）として機能し、ＣＰＵからの指令によって、図１に示すように、入力受付手段が入力受付ステップＳ１を実行し、範囲規定手段が範囲規定ステップＳ２を実行し、素数判定手段が素数判定ステップＳ３を実行し、結果出力手段が結果出力ステップＳ４を実行することで、素数判定を行う。なお、素数判定手段は、さらに第一判定手段および第二判定手段に細分され、それぞれ第一判定ステップＳ３ａおよび第二判定ステップＳ３ｂを実行する。
【００２３】
本プログラムを実行すると、まず入力受付手段が機能して、入力受付ステップＳ１が実行される。入力受付ステップＳ１では、記憶装置に保存されている入出力フォームを読み込んで出力装置に表示する。入出力フォームは、対象数Ｎを入力するための入力部と、対象数Ｎが素数であるか非素数であるかの判定結果を出力するための出力部とを備える。使用者は、任意の正の整数を対象数Ｎとして入力装置から入力する。入力値は記憶装置に保存されると共に、そのまま入力部に表示される。
【００２４】
次に、範囲規定手段が機能して、範囲規定ステップＳ２が実行される。範囲規定ステップＳ２は、対象数Ｎを除する除数の範囲、すなわち、配列の何行目までを除数とするかを定めるものであり、入力された対象数Ｎおよび素数階乗数Ｍ３（＝３０）を記憶装置から読み込み、Ｎ1/2／３０の小数点以下を切り上げた規定数Ｒを算出する。
【００２５】
次に、素数判定手段が機能して、素数判定ステップＳ３が実行される。素数判定ステップＳ３は、対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定するものであり、第一判定ステップＳ３ａおよび第二判定ステップＳ３ｂからなる。
【００２６】
まず、素数判定手段のうち第一判定手段が機能して、第一判定ステップＳ３ａが実行される。第一判定ステップＳ３ａでは、まず対象数Ｎ＝１であれば非素数と判定する。そして、Ｎ≠１であれば、さらに対象数Ｎが、３０以下の素数、すなわち、２，３，５，７，１１，１３，１７，１９，２３，２９であれば素数と判定する。これらの数について対象数Ｎと直接比較して素数判定を行うのは、対象数Ｎとしてこれらの数を入力した場合に、これらの数で割り切れることにより非素数と判定されることを防ぐためである。素数または非素数の判定がなされた場合、判定結果は記憶装置に保存される。
【００２７】
第一判定ステップＳ３ａにおいて素数または非素数の判定がなされなければ、次に、素数判定手段のうち第二判定手段が機能して、第二判定ステップＳ３ｂが実行される。第二判定ステップＳ３ｂでは、除数を第１行の素数およびＲ≧２なら第２行から第Ｒ行までの出現列の数として、対象数Ｎが各除数で割り切れるか否かにより素数判定を行う。ここで出現列は、第１列、および３０以下で最初の三個の素数を除いた素数列、すなわち、第７，１１，１３，１７，１９，２３，２９列となる。上述のとおり、配列のＡ行Ｂ列の値Ｘは、Ｘ＝Ｂ＋３０×（Ａ−１）で与えられるので、まずＡ＝１とし、Ｂを２，３，５，７，１１，１３，１７，１９，２３，２９（１は素数ではないので、Ｂ＝１は含まない）と変化させて、順次対象数Ｎが割り切れるか否かを計算する。何れの数でも割り切れなければ、次はＡ＝２とし、Ｂを１，７，１１，１３，１７，１９，２３，２９（出現列に対応しており、以下においてＢ＝２，３，５は含まない）と変化させて、順次対象数Ｎが割り切れるか否かを計算する。また何れの数でも割り切れなければ、Ａの値を１ずつ大きくして、Ａ＝Ｒとなるまで同様の計算を繰り返す。そして、途中何れかの数で割り切れた場合には、その時点で計算を終了して非素数と判定し、最後まで何れの数でも割り切れない場合には素数と判定し、判定結果は記憶装置に保存される。なお、配列の各値はその都度計算で求めるものであり、記憶装置内に表２に示すような配列自体が記憶されているわけではない。
【００２８】
次に、結果出力手段が機能して、結果出力ステップＳ４が実行される。結果出力ステップＳ４では、素数判定の結果を記憶装置から読み込み、その結果に応じて、出力部に「素数」または「非素数」と表示する。以上でプログラムの全ステップが終了する。
【００２９】
なお、上記の素数判定装置および素数判定プログラムは、本発明の素数判定方法を実施するための一例であり、上記内容に限定されるものではない。また、本発明の素数判定プログラムは、専用のソフトウェアとして実行されるものであっても、汎用の表計算ソフトウェアなどの上で実行されるものであっても良い。
【符号の説明】
【００３０】
Ｓ１ 入力受付ステップ
Ｓ２ 範囲規定ステップ
Ｓ３ 素数判定ステップ
Ｓ４ 結果出力ステップ
【技術分野】
【０００１】
本発明は、対象数が素数であるか否かを判定する素数判定方法、素数判定装置および素数判定プログラムに関する。
【背景技術】
【０００２】
ある正の整数（対象数Ｎ）が素数であるか否かを判定する方法として最も単純なものは、Ｎを２以上Ｎ未満の整数で順次割り算し、割り切れる整数がなければ素数、一つでも割り切れる整数があれば非素数とするものである。しかし、この方法は計算量が非常に多くなるため、従来、もっと少ない計算量で素数判定を行うための種々の方法が提案されている。たとえば、古くから周知の方法として「エラトステネスのふるい」があり、この方法は、対象数Ｎについて、Ｎの平方根Ｎ1/2以下のすべての素数で割り切れなければＮを素数とするものである。また近年では、素数判定はコンピュータシステムにおける暗号技術とも深く関係している。たとえば特許文献１において、対象数Ｎの平方根Ｎ1/2以下の全ての素数が予め記憶されている素数記憶手段と、素数記憶手段内の何れの素数でも割り切れない正の整数αが予め記憶されている整数記憶手段とを用い、対象数Ｎと整数αとを乗算し（乗算結果ｍ＝Ｎα）、乗算結果ｍを素数記憶手段内の何れかの素数で割り算して余りｒを算出し、余りｒが素数記憶手段の何れの素数で割った場合も０でないとき、対象数Ｎを素数であると判定する素数判定方法が提案されており、これにより、素数判定時に電力解析やタイミング解析を施されても、素数候補の漏洩を阻止できる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００２−２６８５４８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、「エラトステネスのふるい」や文献１の方法は、いずれも対象数Ｎの平方根Ｎ1/2以下の素数が既知であることを前提とし、予め用意された素数のリストを参照するものであり、対象数Ｎが大きくなると必要な素数のリストも大きくなること、逆に言えば、既知の素数の最大値の二乗の数までしか対象にできないことが問題であった。
【０００５】
本発明は、上記事情を鑑みたものであり、所定の範囲の既知の素数のみに基づき、大きな対象数についても判定可能な素数判定方法、素数判定装置および素数判定プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のうち請求項１の発明は、対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定方法であって、入力受付手段が、対象数Ｎの入力を受け付ける入力受付過程と、範囲規定手段が、対象数Ｎを除する除数の範囲を定める範囲規定過程と、素数判定手段が、対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定過程と、結果出力手段が、対象数Ｎが素数であるか否かの結果を出力する結果出力過程と、を備え、前記範囲規定過程は、範囲規定手段が、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとして、Ｎ1/2／ＭＰの小数点以下を切り上げた規定数Ｒを算出するものであり、前記素数判定過程は、素数判定手段が、整数を１からＭＰ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭＰを構成する素数を除いた素数列の数を除数とするものであることを特徴とする。
【０００７】
本発明のうち請求項２の発明は、対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定装置であって、対象数Ｎの入力を受け付ける入力受付手段と、対象数Ｎを除する除数の範囲を定める範囲規定手段と、対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定手段と、対象数Ｎが素数であるか否かの結果を出力する結果出力手段と、を備え、前記範囲規定手段が、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとして、Ｎ1/2／ＭＰの小数点以下を切り上げた規定数Ｒを算出するものであり、前記素数判定手段が、整数を１からＭＰ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭＰを構成する素数を除いた素数列の数を除数とするものであることを特徴とする。
【０００８】
本発明のうち請求項３の発明は、対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定プログラムであって、対象数Ｎの入力を受け付ける入力受付ステップと、対象数Ｎを除する除数の範囲を定める範囲規定ステップと、対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定ステップと、対象数Ｎが素数であるか否かの結果を出力する結果出力ステップと、をコンピュータに実行させるためのものであって、前記範囲規定ステップが、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとして、Ｎ1/2／ＭＰの小数点以下を切り上げた規定数Ｒを算出するものであり、前記素数判定ステップが、整数を１からＭＰ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭＰを構成する素数を除いた素数列の数を除数とするものであることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、配列の第１行の素数、すなわちＭＰ以下の素数さえ予め把握されていれば、対象数Ｎがどれだけ大きくなっても、それ以上除数としての素数を算出する必要がない。よって、巨大な整数についても、コンピュータの性能に制限されることなく、容易に素数判定を行うことができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の素数判定プログラムの処理の流れを示すフローチャート。
【発明を実施するための形態】
【００１１】
以下、本発明の素数判定方法について、具体的に説明する。この素数判定方法は、正の整数である対象数Ｎに対して除数を定め、何れかの除数で割り切れた場合には非素数と判定し、何れの除数でも割り切れない場合には素数と判定するものであり、除数の規定方法に特徴がある。そこで、まず除数の規定方法の前提となる考え方について説明する。
【００１２】
まず、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとする。たとえば、Ｍ２＝２×３＝６、Ｍ３＝２×３×５＝３０、Ｍ４＝２×３×５×７＝２１０である。
【００１３】
次に、整数を１からＭＰ列に並べた配列を考える。以下の表１に示すのは、Ｍ２＝６の場合である。ここで、配列中の素数（白抜き文字で表示）の位置に注目すると、最初の二つの素数（２，３）以外の素数は、第１列および第５列に現れることがわかる。
【００１４】
【表１】
【００１５】
同様に、以下の表２に示すのは、Ｍ３＝３０の場合である。ここで、配列中の素数の位置に注目すると、最初の三つの素数（２，３，５）以外の素数は、第１列、第７列、第１１列、第１３列、第１７列、第１９列、第２３列、第２９列に現れることがわかる。
【００１６】
【表２】
【００１７】
すなわち、整数を１からＭＰ列に並べた配列において、素数は、第１行に現れる最初のＰ個の素数を除いて、第１列および最初のＰ個の素数を除いた素数列に現れ、それ以外の列には現れない。以下、第１列および最初のＰ個の素数を除いた素数列を、出現列とよぶ。
【００１８】
ここで、「エラトステネスのふるい」によれば、対象数Ｎについて、Ｎの平方根Ｎ1/2以下のすべての素数で割り切れなければＮを素数と判定できるが、そのためには、除数としてＮ1/2以下のすべての素数が予め把握されていなければならなかった。しかし、上記の配列を考えると、出現列にはすべての素数（最初のＰ個を除く）が含まれている。よって、対象数Ｎに対して、Ｎ1/2／ＭＰの小数点以下を切り上げた数を規定数Ｒとして、除数を、第１行の素数および第２行から第Ｒ行の出現列の数とすれば、その中にはＮ1/2以下のすべての素数が含まれていることになるので、素数判定を行うことができる。その際、配列のＡ行Ｂ列の値Ｘは、Ｘ＝Ｂ＋ＭＰ×（Ａ−１）で与えられるので、容易に求めることができる。なお、出現列には非素数も含まれているが、それらは必ずその数より小さい素数の倍数となっているから、素数判定に影響はない。
【００１９】
このように、本発明の素数判定方法によれば、対象数Ｎがどれだけ大きくなっても、配列の第１行の素数、すなわちＭＰ以下の素数さえ予め把握されていれば、それ以上の除数を求めることは容易であり、従来の方法のように、除数としての素数を算出する必要がない。よって、巨大な整数についても、コンピュータの性能に制限されることなく、容易に素数判定を行うことができる。
【００２０】
実際に本発明の素数判定方法を実施するには、以下に示す素数判定装置および素数判定プログラムを利用する。なお、ここではＰ＝３（Ｍ３＝３０）とした場合の例を示す。
【００２１】
本発明の素数判定プログラムは、キーボードやマウスなどからなる入力装置、ディスプレイなどからなる出力装置、本プログラムの命令を順番に実行するＣＰＵ、本プログラム、本プログラムの実行に必要なデータおよび判定結果などを保存しておく記憶装置を構成要素とする標準的なコンピュータにより実行される。また、本発明の素数判定装置は、前記プログラムが実行されるコンピュータにより構成される。
【００２２】
本プログラムをコンピュータに実行させた場合、コンピュータが各種の手段（入力受付手段、範囲規定手段、素数判定手段、結果出力手段）として機能し、ＣＰＵからの指令によって、図１に示すように、入力受付手段が入力受付ステップＳ１を実行し、範囲規定手段が範囲規定ステップＳ２を実行し、素数判定手段が素数判定ステップＳ３を実行し、結果出力手段が結果出力ステップＳ４を実行することで、素数判定を行う。なお、素数判定手段は、さらに第一判定手段および第二判定手段に細分され、それぞれ第一判定ステップＳ３ａおよび第二判定ステップＳ３ｂを実行する。
【００２３】
本プログラムを実行すると、まず入力受付手段が機能して、入力受付ステップＳ１が実行される。入力受付ステップＳ１では、記憶装置に保存されている入出力フォームを読み込んで出力装置に表示する。入出力フォームは、対象数Ｎを入力するための入力部と、対象数Ｎが素数であるか非素数であるかの判定結果を出力するための出力部とを備える。使用者は、任意の正の整数を対象数Ｎとして入力装置から入力する。入力値は記憶装置に保存されると共に、そのまま入力部に表示される。
【００２４】
次に、範囲規定手段が機能して、範囲規定ステップＳ２が実行される。範囲規定ステップＳ２は、対象数Ｎを除する除数の範囲、すなわち、配列の何行目までを除数とするかを定めるものであり、入力された対象数Ｎおよび素数階乗数Ｍ３（＝３０）を記憶装置から読み込み、Ｎ1/2／３０の小数点以下を切り上げた規定数Ｒを算出する。
【００２５】
次に、素数判定手段が機能して、素数判定ステップＳ３が実行される。素数判定ステップＳ３は、対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定するものであり、第一判定ステップＳ３ａおよび第二判定ステップＳ３ｂからなる。
【００２６】
まず、素数判定手段のうち第一判定手段が機能して、第一判定ステップＳ３ａが実行される。第一判定ステップＳ３ａでは、まず対象数Ｎ＝１であれば非素数と判定する。そして、Ｎ≠１であれば、さらに対象数Ｎが、３０以下の素数、すなわち、２，３，５，７，１１，１３，１７，１９，２３，２９であれば素数と判定する。これらの数について対象数Ｎと直接比較して素数判定を行うのは、対象数Ｎとしてこれらの数を入力した場合に、これらの数で割り切れることにより非素数と判定されることを防ぐためである。素数または非素数の判定がなされた場合、判定結果は記憶装置に保存される。
【００２７】
第一判定ステップＳ３ａにおいて素数または非素数の判定がなされなければ、次に、素数判定手段のうち第二判定手段が機能して、第二判定ステップＳ３ｂが実行される。第二判定ステップＳ３ｂでは、除数を第１行の素数およびＲ≧２なら第２行から第Ｒ行までの出現列の数として、対象数Ｎが各除数で割り切れるか否かにより素数判定を行う。ここで出現列は、第１列、および３０以下で最初の三個の素数を除いた素数列、すなわち、第７，１１，１３，１７，１９，２３，２９列となる。上述のとおり、配列のＡ行Ｂ列の値Ｘは、Ｘ＝Ｂ＋３０×（Ａ−１）で与えられるので、まずＡ＝１とし、Ｂを２，３，５，７，１１，１３，１７，１９，２３，２９（１は素数ではないので、Ｂ＝１は含まない）と変化させて、順次対象数Ｎが割り切れるか否かを計算する。何れの数でも割り切れなければ、次はＡ＝２とし、Ｂを１，７，１１，１３，１７，１９，２３，２９（出現列に対応しており、以下においてＢ＝２，３，５は含まない）と変化させて、順次対象数Ｎが割り切れるか否かを計算する。また何れの数でも割り切れなければ、Ａの値を１ずつ大きくして、Ａ＝Ｒとなるまで同様の計算を繰り返す。そして、途中何れかの数で割り切れた場合には、その時点で計算を終了して非素数と判定し、最後まで何れの数でも割り切れない場合には素数と判定し、判定結果は記憶装置に保存される。なお、配列の各値はその都度計算で求めるものであり、記憶装置内に表２に示すような配列自体が記憶されているわけではない。
【００２８】
次に、結果出力手段が機能して、結果出力ステップＳ４が実行される。結果出力ステップＳ４では、素数判定の結果を記憶装置から読み込み、その結果に応じて、出力部に「素数」または「非素数」と表示する。以上でプログラムの全ステップが終了する。
【００２９】
なお、上記の素数判定装置および素数判定プログラムは、本発明の素数判定方法を実施するための一例であり、上記内容に限定されるものではない。また、本発明の素数判定プログラムは、専用のソフトウェアとして実行されるものであっても、汎用の表計算ソフトウェアなどの上で実行されるものであっても良い。
【符号の説明】
【００３０】
Ｓ１ 入力受付ステップ
Ｓ２ 範囲規定ステップ
Ｓ３ 素数判定ステップ
Ｓ４ 結果出力ステップ
【特許請求の範囲】
【請求項１】
対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定方法であって、
入力受付手段が、対象数Ｎの入力を受け付ける入力受付過程と、
範囲規定手段が、対象数Ｎを除する除数の範囲を定める範囲規定過程と、
素数判定手段が、対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定過程と、
結果出力手段が、対象数Ｎが素数であるか否かの結果を出力する結果出力過程と、を備え、
前記範囲規定過程は、範囲規定手段が、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとして、Ｎ1/2／ＭＰの小数点以下を切り上げた規定数Ｒを算出するものであり、
前記素数判定過程は、素数判定手段が、整数を１からＭＰ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭＰを構成する素数を除いた素数列の数を除数とするものであることを特徴とする素数判定方法。
【請求項２】
対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定装置であって、
対象数Ｎの入力を受け付ける入力受付手段と、
対象数Ｎを除する除数の範囲を定める範囲規定手段と、
対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定手段と、
対象数Ｎが素数であるか否かの結果を出力する結果出力手段と、を備え、
前記範囲規定手段が、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとして、Ｎ1/2／ＭＰの小数点以下を切り上げた規定数Ｒを算出するものであり、
前記素数判定手段が、整数を１からＭＰ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭＰを構成する素数を除いた素数列の数を除数とするものであることを特徴とする素数判定装置。
【請求項３】
対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定プログラムであって、
対象数Ｎの入力を受け付ける入力受付ステップ（Ｓ１）と、
対象数Ｎを除する除数の範囲を定める範囲規定ステップ（Ｓ２）と、
対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定ステップ（Ｓ３）と、
対象数Ｎが素数であるか否かの結果を出力する結果出力ステップ（Ｓ４）と、をコンピュータに実行させるためのものであって、
前記範囲規定ステップ（Ｓ２）が、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとして、Ｎ1/2／ＭＰの小数点以下を切り上げた規定数Ｒを算出するものであり、
前記素数判定ステップ（Ｓ３）が、整数を１からＭＰ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭＰを構成する素数を除いた素数列の数を除数とするものであることを特徴とする素数判定プログラム。
【請求項１】
対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定方法であって、
入力受付手段が、対象数Ｎの入力を受け付ける入力受付過程と、
範囲規定手段が、対象数Ｎを除する除数の範囲を定める範囲規定過程と、
素数判定手段が、対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定過程と、
結果出力手段が、対象数Ｎが素数であるか否かの結果を出力する結果出力過程と、を備え、
前記範囲規定過程は、範囲規定手段が、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとして、Ｎ1/2／ＭＰの小数点以下を切り上げた規定数Ｒを算出するものであり、
前記素数判定過程は、素数判定手段が、整数を１からＭＰ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭＰを構成する素数を除いた素数列の数を除数とするものであることを特徴とする素数判定方法。
【請求項２】
対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定装置であって、
対象数Ｎの入力を受け付ける入力受付手段と、
対象数Ｎを除する除数の範囲を定める範囲規定手段と、
対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定手段と、
対象数Ｎが素数であるか否かの結果を出力する結果出力手段と、を備え、
前記範囲規定手段が、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとして、Ｎ1/2／ＭＰの小数点以下を切り上げた規定数Ｒを算出するものであり、
前記素数判定手段が、整数を１からＭＰ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭＰを構成する素数を除いた素数列の数を除数とするものであることを特徴とする素数判定装置。
【請求項３】
対象数Ｎ（Ｎは正の整数）が素数であるか否かを判定する素数判定プログラムであって、
対象数Ｎの入力を受け付ける入力受付ステップ（Ｓ１）と、
対象数Ｎを除する除数の範囲を定める範囲規定ステップ（Ｓ２）と、
対象数Ｎを除数で除して、対象数Ｎが素数であるか否かを判定する素数判定ステップ（Ｓ３）と、
対象数Ｎが素数であるか否かの結果を出力する結果出力ステップ（Ｓ４）と、をコンピュータに実行させるためのものであって、
前記範囲規定ステップ（Ｓ２）が、小さいほうからＰ（Ｐは２以上の整数）個の素数を掛け合わせた数を素数階乗数ＭＰとして、Ｎ1/2／ＭＰの小数点以下を切り上げた規定数Ｒを算出するものであり、
前記素数判定ステップ（Ｓ３）が、整数を１からＭＰ列に並べた配列において、第１行の素数およびＲ≧２なら第２行から第Ｒ行までの第１列およびＭＰを構成する素数を除いた素数列の数を除数とするものであることを特徴とする素数判定プログラム。
【図１】
【公開番号】特開２０１２−７８４５５（Ｐ２０１２−７８４５５Ａ）
【公開日】平成２４年４月１９日（２０１２．４．１９）
【国際特許分類】
【出願番号】特願２０１０−２２１８４１（Ｐ２０１０−２２１８４１）
【出願日】平成２２年９月３０日（２０１０．９．３０）
【出願人】（５９６０９２８７２）
【Ｆターム（参考）】
【公開日】平成２４年４月１９日（２０１２．４．１９）
【国際特許分類】
【出願日】平成２２年９月３０日（２０１０．９．３０）
【出願人】（５９６０９２８７２）
【Ｆターム（参考）】
[ Back to top ]