プログラミングのお題スレ Part22 (831ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
759: 04/17(木)00:27 ID:dz0qzhSq(1/3) AAS
素因数和2025のお題の3系統のコードを読み解いてみた
>>756
2000万まで各々で素因数の和を求めて2025になるかを確認する方法。
ただし各数の素因数分解を工夫せずにすると大変なので、
各数の最小素因数(SPF)を先に一気にエラトステネスの篩で求めてる。
それを用いれば各数の素因数分解はその分解数回の割算だけで求まる。
ただしそのSPF表のために長さ2000万のベクタを用いている。
省4
760: 04/17(木)00:29 ID:dz0qzhSq(2/3) AAS
>>741
2000万個すべてを素因数分解する方法とは逆に、
2025以下の素数の組み合わせを調べていく方法。
そのうち和が2025になる組み合わせの積が各解となる。
それを効率よく求めるために2025(+1)個のベクタのベクタpを用意している。
つまり和がsumとなる時の積をp[sum]に記録していく。
効率面からの仮の初期値p[0]に1を入れて、各素数iについて降順に、
省5
761: 04/17(木)00:32 ID:dz0qzhSq(3/3) AAS
>>738
これも2025以下の素数を組み合わせて和が2025になる解を調べる方法。
解一覧を収めるベクタ以外は、固定の長さ305のベクタのみが使われている。
この長さの 305 とは2025以下～3以上の素数[2017, 2011, ... 5, 3]の数になってる。
各素数の冪乗の和 2017^e2017 + 2011^e2011 + ... + 5^e5 + 3^e3 及び積を計算していくが、
各指数のe2017などは解に不要なので使われておらず、
各冪乗の和自体も不要なので2025までの残りの数が使われていて、
省10
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.035s