素因数分解

A入力数値を素因数分解し結果をカンマ区切りでCへ出力します
ホームへ

内部処理：

内部では
１：試し割で素数30029までの素数を取り出し、その後以下の順で素因数分解を試みます
２：フェルマーのアルゴリズム（ループ最大は１００００００回から１００００回に変更）
３：ポラードのp-1法（ループ最大は１００００回）
４：ウィリアムズのp+1法（ループ最大は１００００回）
５：ポラードの ρ 法（ループ最大は５００００００回）１４桁の素数までは対応できそうです
の順で行われます最後まで成功しなかった場合１分以上待たされる事もあります
答えが出なかった場合も取り出した素数と残った合成数をカンマ区切りでCへ出力します
※二次ふるい法はメモリを使わずに高速化ができそうにないので諦めました

大整数電卓ツール使ってみてください

高速化：

フェルマーのアルゴリズムの高速化で 参考サイトでは二乗計算を足し算に置き換えて 高速化をしていますが、ここではY 側の処理に注目し高速化を試みました Y 側の終了は元の合成数より小さくなるか等しくなるまでループします、このループ回数は
m:X側からの数値でこれのみが変数　n:元の合成数とすると
Y 側ループ回数を求める式は：r(1+m-n)-1 になり
　1+m-n＝N×N　となる時が答えなのです
ここまででサイトにアップしていましたが今回更に高速化ということで
　1+m-n＝N×N　に注目し、平方根が余りのない整数の時が答えになるので平方根を計算する前に値が整数の二乗かを試し、 そうでなければ何も計算せずX 側のループへ戻します、具体的には整数の二乗の平方剰余がとる値は決まっているので、 それを使って判断しています但し剰余を試す数値は複数
（256,97,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67） を試し結果として１０万分の一以下まで無駄なルート計算を抑えることができました
実験では４０万回ループするデータで最後まで残ったのは２個でそのうち一個は正解なので 無駄なルート計算をしたのは一回のみでした。
今回更に見直して素数同士の差に注目し合成数をN 差をK 和をH とすると √（H×H－４N）でKが求まるので√が整数になるHを探し答えKが求まると （H＋K）÷２と（H－K）÷２が素数の答えになります。これによりほんの数パーセントですが高速化できました。
更に見直して最初からHとKは２の倍数なので先に２で割り√（H×H－A)でKを求めます。
ここで素数をそれぞれ(2*n+1)と(2*m+1)と置くと
(2*n+1)*(2*m+1)=4nm+2*n+2*m+1=a なので (a-1)%4=0 なら(2*n+2*m)も４で割り切れ故に((2*n+1)+(2*m+1))/2=H
((2*n+1)-(2*m+1))/2=Kなので H%2=1 K%2=0 となる
(a-1)%4=2 なら H%2=0 K%2=1 となるのでHの初期値を(A-1)%4により、それぞれ偶数または奇数に固定して２個飛ばしでループさせれば
ループ回数は二分の一となります。結果（H＋K）と（H－K）が素数の答えになります
これでも８桁×８桁の素数で３秒弱かかります、まだまだですね。

私見：

個人的に好きなのはフェルマーのアルゴリズムで他でも１０桁の素数が答えとして表示されるのは「すごいな」とは思いますが２０００桁の合成数から１０００桁の 素数が0.079秒で出力された時は「おおぉぉ！」と声が出てしまいます、頭では直ぐに答えが出ると分かっていても、やっぱり感動してしまいます。 「大整数電卓」には「C数式計算」の例として「フェルマ素因数分解実験用合成数作成」がありますが １００桁の素数なら素数を作るのも一瞬ですが１０００桁だと 素数を見つけるだけでも大変です次の素数まで１万以上離れてることがあるので運が悪ければ一つの素数を得るのに３分以上かかる事もあります、そうやって時間をかけて 作った合成数が一瞬で素因数分解できるのは感動です（勿論前提として上位５００桁が同じで下位５００桁のみが違う素数同士を掛け合わせた合成数である事）
ただ悲しいのは、これが役立つ場面を思いつかないということです

注１：
素数関連の大部分をこのサイトを参考に作成しました

参考実験：フェルマーのアルゴリズム

２０２２年９月１０日追記：多少アルゴリズムに手を加えて高速化をしてみました。なのでループ最大を１０００回から１００００回に変更しました
※３００２９までの素数試し割の時間も含んだ時間です

１００桁の素数２個

で合成数を作り(上位指定桁は同じ数字)素因数分解を実行し掛かる時間を測定
実験：
上位５０桁下位５０桁で作成　
ループ回数 １　　時間：0.002秒
合成数：52858573889305743368658801063041665538718710338038853961324172302766003175664506178472769865011015541977383988386619930788475147151430487787352101919076418548905001687630451627636550434944086829403743
素数１：7270390215752229028954049927225296301029984559592760155262844718140352046233180312909284722021061017
素数２：7270390215752229028954049927225296301029984559592777181805164002077510013670899123190287390083140279
実験：
上位４９桁下位５１桁で作成　
ループ回数 ３　　時間：0.002秒
合成数：72832157829248889731356108622846985599381920392691908622628397724361218318867137880127433525501869724997613003147033165943836923219760802646755876706310814947760304639628990816636082052143567580019899
素数１：8534175872880104275555614251992984532274548096045090862962962798491207089453308687259968275080787221
素数２：8534175872880104275555614251992984532274548096045520695538628190226546298414171566902547726239448719
実験：
上位４８桁下位５２桁で作成　
ループ回数２０３　時間：0.024秒（高速化で0.002秒）
合成数：82357115638223436220151206427545901491774666127458816854641975199618335823958431965195090693490876974828212163655663910630553917152066492408207554437566472405994717839523700408514727323013969250060877
素数１：9075082128456107598762172452148705589894531871820970404759524024151044563722727343056662057892088049
素数２：9075082128456107598762172452148705589894531871824800591582544332596504513680002949878798823799551773
実験：
上位４７桁下位５３桁で作成　
ループ回数１９１７５　時間：ループ回数：1.782秒（高速化で0.014秒）
合成数：42921444914596261758088196610731424550473736982628240796451549688266970428034284693073033661905352838442717888885427557015880559390817049676688167524272347718174081925415724656422849975091418840546379
素数１：6551446017071060454948960241312316634969077078751047396068281086181522771123058901689200690737926697
素数２：6551446017071060454948960241312316634969077078719346180193868480170072197497360433499581680483463507
実験：
上位４６桁下位５４桁で作成　
ループ回数２３３５９８１　時間：解答なし （高速化で1.238秒　※実験のためループ最大を更に上げてます本来は解答なしです）
合成数：39213050304637444684036553893543655495609342688871264495680980780311335917803385323701179053280481670953924866015868928357336836947650062515939026249962399260563894015735497075880912433492669209115639
素数１：6262032441998160447093109335698069371780834996497565828100454428349887209533407287853294122489757957
素数２：6262032441998160447093109335698069371780834996155478274562613856218040715589956147240580750909524427

１０桁の素数２個

で合成数を作り(上位は同じ数字)素因数分解を実行し掛かる時間を測定
実験：
上位５桁下位５桁で作成　
ループ回数 １　　時間：0.000秒
合成数：1154438269757072357
素数１：1074421109
素数２：1074474673
実験：
上位４桁下位６桁で作成　
ループ回数 ９　　時間：0.001秒
合成数：12022413297471709849
素数１：3467573971
素数２：3467096419
実験：
上位３桁下位７桁で作成　
ループ回数 ５７２　時間：0.004秒（高速化で0.001秒）ループ回数を計算しないでオリジナルのままループを回すと58.508秒でした
合成数：33702924732749238353
素数１：5807998327
素数２：5802846839
実験：
上位２桁下位８桁で作成　
ループ回数 ９７２６　時間：0.067秒です（高速化で0.005秒）
合成数：27164434013085267377
素数１：5201892133
素数２：5222029469
実験：
上位１桁下位９桁で作成　
ループ回数　４５４３３５８　時間：解答なし（高速化で1.457秒　※実験のためループ最大を更に上げてます本来は解答なしです）
合成数：19345006149443720197
素数１：4602805939
素数２：4202872423

因みに普通の素因数分解

も７桁×７桁までならできます
実験：
７桁×７桁で作成　
ループ回数　391854　時間：解答なし（高速化で0.141秒）
合成数：44644177321333
素数１：4751849
素数２：9395117
実験：
７桁×７桁で作成　
ループ回数　915229　時間：解答なし（高速化で0.28秒）
合成数：10997982970057
素数１：1603237
素数２：6859861