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

**１３２人目の素数さん** · 2023/12/03(日) 10:16:30.08

どうすればいい？

**１３２人目の素数さん** · 2023/12/03(日) 10:31:42.62

テーブルを使う

**１３２人目の素数さん** · 2023/12/03(日) 10:39:20.18

巨大数も扱えるようにしてほしい

**１３２人目の素数さん** · 2023/12/03(日) 13:09:06.29

素因数分解って総当たり以外に方法あるの？

**BLACKX** ◆SvoRwjQrNc · 2023/12/05(火) 13:04:53.48

平方数で当たりをつけるとか？

**BLACKX** ◆SvoRwjQrNc · 2023/12/05(火) 13:18:33.47

例えば2021の素因数分解をすると
40×40=1600 50×50=2500の間にあるから40～50の間の素数が使われると仮定
その間の素数は41.43.47の3つ
下一桁が1なので41は除外で43×47=2021

この方法が巨大数に応用できればログが少なくて実用的になると良いなぁ…

**１３２人目の素数さん** · 2023/12/05(火) 13:27:35.72

shorのアルゴリズム

**１３２人目の素数さん** · 2023/12/05(火) 14:33:58.59

>>6
よくわからん
77で試すと
8^2<77<9^2だけど8と9の間に77の素因数はないが
うまく行く場合といけない場合があるんか

**１３２人目の素数さん** · 2023/12/05(火) 16:10:48.07

アルゴリズムを考える時に一番重要なのは現在のコンピュータの演算速度
例えば足し算引き算掛け算は1サイクルで済むけど
割り算や余りは数十サイクルもかかってしまう

**１３２人目の素数さん** · 2023/12/05(火) 19:10:08.98

>>6
フェルマーのやり方と似てる
平方根をとって総当たりでやる

**BLACKX** ◆SvoRwjQrNc · 2023/12/05(火) 20:24:01.79

>>8
あるある
あとはその素数の差が極端に離れてるとか
3つの素数の場合は1つだけこれで特定できたり出来なかったり

**BLACKX** ◆SvoRwjQrNc · 2023/12/06(水) 13:16:14.89

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

**１３２人目の素数さん** · 2023/12/06(水) 14:11:00.46

PRIMES is in P に憧れる

**１３２人目の素数さん** · 2023/12/06(水) 17:21:53.66

>>12
多分最小の反例は14かな

**BLACKX** ◆SvoRwjQrNc · 2023/12/06(水) 18:43:28.82

>>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にはならないが。

**BLACKX** ◆SvoRwjQrNc · 2023/12/06(水) 19:18:04.03

>>14
ごめんなさい
今やっとわかった
このやり方で14は3.74だから出来ないね

**１３２人目の素数さん** · 2023/12/07(木) 00:29:22.28

平方根からずらしていってデータを集める系は複数多項式2次ふるい法っていうんじゃね？

**BLACKX** ◆SvoRwjQrNc · 2023/12/07(木) 08:17:04.37

>>17
調べたらそれだった

**１３２人目の素数さん** · 2023/12/07(木) 10:59:04.58

篩法とかとは別のアプローチで考えてみたい

**１３２人目の素数さん** · 2023/12/08(金) 23:24:16.78

>>19
p法みたいなのとか?

**１３２人目の素数さん** · 2023/12/11(月) 19:21:45.05

2で終わってた

**BLACKX** ◆SvoRwjQrNc · 2023/12/11(月) 19:53:52.69

>>19
https://i.imgur.com/AmCfa9S.jpg
図形で捉える的な？
それをアルゴリズムに落とせるか否かだけど…
最低限の篩は必要だと思うよ

**１３２人目の素数さん** · 2023/12/11(月) 20:06:17.00

擬素数を使って絞れないだろうか

**BLACKX** ◆SvoRwjQrNc · 2023/12/11(月) 20:12:14.89

>>23
それってどうやるんだ？
試しに2501でやってみてもらいたい

**BLACKX** ◆SvoRwjQrNc · 2023/12/11(月) 20:27:00.78

俺も図形形式でやってみる
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

**BLACKX** ◆SvoRwjQrNc · 2023/12/11(月) 20:29:37.99

てかぶっちゃけ素数を絞るのって勘な左右されない？

**BLACKX** ◆SvoRwjQrNc · 2023/12/11(月) 20:32:43.63

すまん誤投

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

**１３２人目の素数さん** · 2023/12/12(火) 10:51:38.77

https://i.imgur.com/jJBFLRP.jpg

**１３２人目の素数さん** · 2023/12/14(木) 12:51:06.96

正の整数Pが素数であるとは、1ではない正の整数N1とN2をつかって
P=N1*N2と表せないようなもののことである。
それでは
正の整数Qが1ではない正の整数N1、N2、N3を使って
Q=N1＊N2＊N3とは表せないものであるとするとき、
Qを要素とする集合はどのようなものになるか。

**１３２人目の素数さん** · 2023/12/16(土) 07:30:38.97

tiktok liteでPayPayやAmazon券などに交換可能な4000円分のポイントをプレゼント中！
※既存tiktokユーザーの方はtiktokからログアウトしてアンインストールすれば可能性あり
　　　
1.SIMの入ったスマホかタブレットを準備。
2.以下のtiktok liteのサイトからアプリをダウンロード（ダウンロードだけでまだ起動しない)
https://lite.tiktok.com/t/ZSNfGY43n/
3.ダウンロード完了後、もう一度上記アドレスのリンクからアプリへ
4.アプリ内でtiktokで使用してない電話番号かメールアドレスから登録
5.10日間連続のチェックイン(←重要！)で合計で4000円分のポイントゲット

ポイントはPayPayやAmazon券に交換できます！
家族・友人に紹介したり、通常タスクをこなせば更にポイントを追加でゲットできます

**１３２人目の素数さん** · 2023/12/16(土) 08:10:11.47

>>30
お疲れ様