素因数分解 （正の整数を素数の積の形に分解） と サンプルプログラム
Factoring For VBA Ver.1.23 Alpha Edition （開発中版） [2009/05/26]
VBA Export Files (bas, frm, frx) VBA 6 以降
DownLoad (Factoring123.zip/14KB)
|
概説 |
| |
素因数分解 （正の整数を素数の積の形に分解） するプログラムです。
素因数分解 例１（処理できる数の最大値）
素因数分解 例２（素数の場合／９番目のメルセンヌ素数[M61=261-1]）
|
| ※画像は開発中のバージョンのものです |
|
| |
処理できる数の最大値は、10進型(Decimal/96bit(12byte))最大値の
79,228,162,514,264,337,593,543,950,335 [=(2^96)-1]
です （素因数に大きな数が含まれていると計算に時間がかかります）
|
| |
|
計算時間について
計算時間は数値によって大きく異なります
|
処理できる数の最大値 (79228162514264337593543950335) は、
１秒未満(Pentium 4 2.80C GHz)で素因数分解が出来ますが、
素因数に非常に大きな素数が含まれていると、演算に掛かる時間が極端に大きくなります。
数値Ｘが素数の条件は、２から√Ｘまでの素数で割り切れなければ素数。
このプログラム(Factoring For VBA)では、２から1000未満の素数は、素数リストを使用し、
1000以上（√Ｘまで）は、１位の位が"1,3,7,9"の数で割り切れるかどうかでチェックしている(※)ので、
数値Ｘが素数ならば（素数と確認するまでの）演算時間はほぼ√Ｘに比例します。
９番目のメルセンヌ素数 ： 約９０分
M61[＝(261)-1＝2305843009213693951]は１９桁の素数で、√Ｘは、
√(M61)＝√2305843009213693951＝1518500249.988･･･＝1518500249 (切捨て)。
計算時間（素数と確認できるまでの時間）は、約９０分 （Pentium4 2.80C GHz）。
１０番目のメルセンヌ素数 ： ９番目のメルセンヌ素数の約16384倍
M89[＝(289)-1＝618970019642690137449562111]は２７桁の素数で、√Ｘは、
√(M89)＝√618970019642690137449562111＝24879108095803.7990･･･＝24879108095803 (切捨て)
よって、
√(M89)/√(M61)=24879108095803/1518500249＝16384.00001･･･ 倍
２７桁のM89（を素数と確認出来るまで）に必要な時間 (Pentium4 2.80C GHz)
Ｔ＝90*16384＝1474560(分)＝24576(時間)＝1024(日) で、約2.8年！！掛かると予想される。
| ※ |
理論的には素数のみのチェックで十分であるが、
√(10進型(Decimal)最大値)＝√79228162514264337593543950335≒281474976710655
以下の全ての素数リストを用意することは不可能。
また、その都度、素数チェックをすることも非現実的なので、
1000以上は素数の可能性のある数値（１位の位の数が"1,3,7,9"の数）を
すべてチェックしています
|
|
|
| |
| 計算例（１） |
| 項目 |
値 |
備考 |
| 数値 |
79228162514264337593543950335 |
処理できる数の最大値
[=(2^96)-1]
|
計算時間 |
１秒未満 |
(Pentium 4 2.80C GHz) |
| リスト |
3^2, 5, 7, 13, 17, 97, 193, 241, 257, 673, 65537, 22253377 |
|
| 式（指数） |
3^2 * 5 * 7 * 13 * 17 * 97 * 193 * 241 * 257 * 673 * 65537 * 22253377 |
|
| 式（展開） |
3 * 3 * 5 * 7 * 13 * 17 * 97 * 193 * 241 * 257 * 673 * 65537 * 22253377 |
|
| 電卓 |
:q(3y2)*5*7*17*97*193*241*257*673*65537*22253377= |
|
| |
| 計算例（２） |
| 項目 |
値 |
備考 |
| 数値 |
79228162514264337593543950334 |
処理できる数の最大値−１
[=(2^96)-2]
|
計算時間 |
約２２分 |
(Pentium 4 2.80C GHz) |
| リスト |
2, 31, 191, 524287, 420778751, 30327152671 |
|
| 式（指数） |
2 * 31 * 191 * 524287 * 420778751 * 30327152671 |
|
| 式（展開） |
2 * 31 * 191 * 524287 * 420778751 * 30327152671 |
|
| 電卓 |
:q2*31*191*524287*420778751*30327152671= |
|
| |
| 計算例（３） |
| 項目 |
値 |
備考 |
| 数値 |
123456789123456789123456789 |
{1+(1E+9)+(1E+18)}n
ここに n:123456789
|
計算時間 |
約１分１０秒 |
(Pentium 4 2.80C GHz) |
| リスト |
3^3, 757, 3607, 3803, 440334654777631 |
|
| 式（指数） |
3^3 * 757 * 3607 * 3803 * 440334654777631 |
|
| 式（展開） |
3 * 3 * 3 * 757 * 3607 * 3803 * 440334654777631 |
|
| 電卓 |
:q(3y3)*757*3607*3803*440334654777631= |
|
| |
| 計算例（４） |
| 項目 |
値 |
備考 |
| 数値 |
2305843009213693951 |
９番目のメルセンヌ素数
[M61=261-1]
|
計算時間 |
１時間３０分程度 |
(Pentium 4 2.80C GHz) |
| リスト |
*** |
|
| 式（指数） |
*** |
|
| 式（展開） |
*** |
|
| 電卓 |
*** |
|
| |
| ※電卓の結果（文字式）は、Windowsの電卓に貼り付けると、計算して結果を表示します |
| ※計算時間は数値によって大きく異なります |
|
|
|
|
|
| 使用方法（解説と使用例）はreadme.txtにありますので参照してください |
|
|
| 動作条件 |
| |
VBA 6 以降
Excel 2000 以降
AutoCAD 2000i 以降
|
| |
|
| |
|
|
| 注意事項など |
| |
★必要なエラー処理や動作確認が十分に出来ていない Alpha Edition（開発途中版）です
★動作に致命的な不具合や演算結果が不正確な可能性があります
★必ずデータのバックアップを取った上でご利用下さい
|
| |
|
|
| |
|
|
| その他 |
| |
そのほか使用条件等は上記ファイルに添付されている readme.txt ファイルをお読み下さい。 |
| |
|
| |
|
|
| 更新内容 |
| |
| [2009/05/26] |
Ver.1.23 Alpha Edition |
修 正 |
素因数分解(DecFactoring) 丸め誤差の判定 |
| [2009/05/14] |
Ver.1.22 Alpha Edition |
修 正 |
素因数分解(DecFactoring) チェック終了の判別を平方根から、
割る数と除算の値の比較に変更など若干 |
| 追加変更 |
素因数分解(DecFactoring) 素数リストチェック追加 |
| 抹 消 |
平方根(DecSqr) チェック終了の判別方変更により不要の為
素因数分解(DecFactoring) カウンター |
| そ の 他 |
コメント修正 |
| [2009/05/13] |
Ver.1.21 Alpha Edition |
修 正 |
サンプルプログラム リスト部など |
| [2009/05/13] |
Ver.1.20 Alpha Edition |
修 正 |
変更多々 |
| [2009/05/13] |
Ver.1.10 Alpha Edition |
修 正 |
変更多々 |
| [2009/05/11] |
Ver.1.00 Alpha Edition |
新規公開 |
|
|
|
|
|
|
|
| |
|
|
| 以前のバージョン |
| |
| Ver.1.22 |
Alpha Edition （開発中版） |
[2009/05/14] |
DownLoad (Factoring122.zip/14KB) |
| Ver.1.21 |
Alpha Edition （開発中版） |
[2009/05/13] |
DownLoad (Factoring121.zip/13KB) |
| Ver.1.20 |
Alpha Edition （開発中版） |
[2009/05/13] |
DownLoad (Factoring120.zip/13KB) |
| Ver.1.10 |
Alpha Edition （開発中版） |
[2009/05/13] |
DownLoad (Factoring110.zip/13KB) |
| Ver.1.00 |
Alpha Edition （開発中版） |
[2009/05/11] |
DownLoad (Factoring100.zip/11KB) |
|
|
|
| |
|
|
|
|