最速の素因数分解アルゴリズムを作りたい

最速の素因数分解アル ..

2:１３２人目の素数さん
23/12/03 10:31:42.62 6LXUcjo+.net
テーブルを使う

3:１３２人目の素数さん
23/12/03 10:39:20.18 c1O68NAp.net
巨大数も扱えるようにしてほしい

4:１３２人目の素数さん
23/12/03 13:09:06.29 B/5O97Lf.net
素因数分解って総当たり以外に方法あるの？

5:BLACKX
23/12/05 13:04:53.48 7V/tdYi7.net
平方数で当たりをつけるとか？

6:BLACKX
23/12/05 13:18:33.47 7V/tdYi7.net
例えば2021の素因数分解をすると
40×40=1600 50×50=2500の間にあるから40～50の間の素数が使われると仮定
その間の素数は41.43.47の3つ
下一桁が1なので41は除外で43×47=2021
この方法が巨大数に応用できればログが少なくて実用的になると良いなぁ…

7:１３２人目の素数さん
23/12/05 13:27:35.72 7lG+dYct.net
shorのアルゴリズム

8:１３２人目の素数さん
23/12/05 14:33:58.59 anX7/3R6.net
>>6
よくわからん
77で試すと
8^2<77<9^2だけど8と9の間に77の素因数はないが
うまく行く場合といけない場合があるんか

9:１３２人目の素数さん
23/12/05 16:10:48.07 AlsNqS3R.net
アルゴリズムを考える時に一番重要なのは現在のコンピュータの演算速度
例えば足し算引き算掛け算は1サイクルで済むけど
割り算や余りは数十サイクルもかかってしまう

10:１３２人目の素数さん
23/12/05 19:10:08.98 fERPuIHl.net
>>6
フェルマーのやり方と似てる
平方根をとって総当たりでやる

11:BLACKX ◆SvoRwjQrNc
23/12/05 20:24:01.79 7V/tdYi7.net
>>8
あるある
あとはその素数の差が極端に離れてるとか
3つの素数の場合は1つだけこれで特定できたり出来なかったり

12:BLACKX
23/12/06 13:16:14.89 6NA8l5NP.net
その数を平方で取って区間を素数から素数で取れば良いのかな？
77は√77=8.77...だから7と11になるみたいな？
2021は√2021=44.95...だから43と47
どちらにせよ区間に幅持たせないと飛んでたら意味無いし3つ使ってたら使えるかわからんが…

13:１３２人目の素数さん
23/12/06 14:11:00.46 FidwBQ14.net
PRIMES is in P に憧れる

14:１３２人目の素数さん
23/12/06 17:21:53.66 b4mwad9C.net
>>12
多分最小の反例は14かな

15:BLACKX
23/12/06 18:43:28.82 6NA8l5NP.net
>>14
どういう事？
2.3.5.7.11.13...で
8.77は↑ここの位置だから素数区間は7と11でしょ？
区間を広げたとしても1桁が7だから
該当は
7と11、11と17、3と19が該当で
7と11と見つけられると考えられるが、
反例の14はどこから？
2と7は下一桁が7にはならないが。

16:BLACKX
23/12/06 19:18:04.03 6NA8l5NP.net
>>14
ごめんなさい
今やっとわかった
このやり方で14は3.74だから出来ないね

17:１３２人目の素数さん
23/12/07 00:29:22.28 jOi8bnHq.net
平方根からずらしていってデータを集める系は複数多項式2次ふるい法っていうんじゃね？

18:BLACKX
23/12/07 08:17:04.37 lVx43fUX.net
>>17
調べたらそれだった

19:１３２人目の素数さん
23/12/07 10:59:04.58 EAJWydmP.net
篩法とかとは別のアプローチで考えてみたい

20:１３２人目の素数さん
23/12/08 23:24:16.78 krUaJiCA.net
>>19
p法みたいなのとか?

21:１３２人目の素数さん
23/12/11 19:21:45.05 gXbJZiBP.net
2で終わってた

22:BLACKX
23/12/11 19:53:52.69 uHxiZP2B.net
>>19
URLﾘﾝｸ(i.imgur.com)
図形で捉える的な？
それをアルゴリズムに落とせるか否かだけど…
最低限の篩は必要だと思うよ

23:１３２人目の素数さん
23/12/11 20:06:17.00 p5At9i6C.net
擬素数を使って絞れないだろうか

24:BLACKX ◆SvoRwjQrNc
23/12/11 20:12:14.89 uHxiZP2B.net
>>23
それってどうやるんだ？
試しに2501でやってみてもらいたい

25:BLACKX ◆SvoRwjQrNc
23/12/11 20:27:00.78 uHxiZP2B.net
俺も図形形式でやってみる
2501はだいたい2500なので√2500=50が一旦の上限
50×40=2000
2501-2000=501ではまだ残りが見えてこなさそうなので下1桁に1が出るようにすると
41×51=2091
2501-2091=410でビンゴ
41×10で
51+10=61←素数なので

2501=41×61

26:BLACKX ◆SvoRwjQrNc
23/12/11 20:29:37.99 uHxiZP2B.net
てかぶっちゃけ素数を絞るのって勘な左右されない？

27:BLACKX ◆SvoRwjQrNc
23/12/11 20:32:43.63 uHxiZP2B.net
すまん誤投

てかぶっちゃけ素数を絞るのって匂いというか勘に左右されていかない？
小さいのとの剥離が大きければ大きいほど探しにくくなるわけだし
誰か逆に何桁でも良いから問題出してほしい楽しくなってきた

28:１３２人目の素数さん
23/12/12 10:51:38.77 y5CcJSmf.net
URLﾘﾝｸ(i.imgur.com)

29:１３２人目の素数さん
23/12/14 12:51:06.96 Ojnby9i5.net
正の整数Pが素数であるとは、1ではない正の整数N1とN2をつかって
P=N1*N2と表せないようなもののことである。
それでは
正の整数Qが1ではない正の整数N1、N2、N3を使って
Q=N1＊N2＊N3とは表せないものであるとするとき、
Qを要素とする集合はどのようなものになるか。

30:１３２人目の素数さん
23/12/16 07:30:38.97 dD0bcI5y.net
tiktok liteでPayPayやAmazon券などに交換可能な4000円分のポイントをプレゼント中！
※既存tiktokユーザーの方はtiktokからログアウトしてアンインストールすれば可能性あり
　　　
1.SIMの入ったスマホかタブレットを準備。
2.以下のtiktok liteのサイトからアプリをダウンロード（ダウンロードだけでまだ起動しない)
URLﾘﾝｸ(lite.tiktok.com)
3.ダウンロード完了後、もう一度上記アドレスのリンクからアプリへ
4.アプリ内でtiktokで使用してない電話番号かメールアドレスから登録
5.10日間連続のチェックイン(←重要！)で合計で4000円分のポイントゲット
ポイントはPayPayやAmazon券に交換できます！
家族・友人に紹介したり、通常タスクをこなせば更にポイントを追加でゲットできます

31:１３２人目の素数さん
23/12/16 08:10:11.47 SjYjOj4P.net
>>30
お疲れ様