Namaran

Code daily. Without assist.

2026-11-19

factorize.cpp

#include <vector>

std::vector<int>
factorize(int x,
          const std::vector<int>& spf) {
}

2 以上 x 以下の各整数 k について、k を割り切る最小の素数を spf[k] に入れた表 spf を受け取り、x を素因数分解した結果を返す factorize を書いてください。素因数は小さい順に並べ、同じ素因数は割り切れる回数だけ繰り返します。x が 1 のときは空の std::vector を返します。例の spf は 100 までの表です。

入力例 1

factorize(84, spf)

出力例 1

{2, 2, 3, 7}

入力例 2

factorize(97, spf)

出力例 2

{97}

入力例 3

factorize(1, spf)

出力例 3

{}
Reference

Reference

std::vector<int>
factorize(int x,
          const std::vector<int>& spf) {
    std::vector<int> ps;
    for (; x > 1; x /= spf[x])
        ps.push_back(spf[x]);
    return ps;
}

spf[x] は x を割り切る最小の素数なので、まずそれを結果に加え、x を spf[x] で割ります。割ったあとの x には残りの素因数がそのまま残っていて、次の spf[x] がその中で最小のものです。これを x が 1 になるまで繰り返せば、素因数が小さい順に、割り切れる回数だけ出てきます。1回ごとに表を1回引いて1回割るだけで、x は少なくとも半分になるので、繰り返しは x の桁数に比例する回数で終わります。掲載したのは参考実装で、唯一の正解ではありません。

入力例 1 では、spf[84] = 2 で 42、spf[42] = 2 で 21、spf[21] = 3 で 7、spf[7] = 7 で 1 になり、{2, 2, 3, 7} が返ります。素数の 97 では spf[97] が 97 自身なので、1回で 1 になります。x が 1 なら for の条件 x > 1 が最初から偽で、空の ps を返します。引数の x は値渡しなので、関数の中で割っていっても呼び出し側の変数は変わりません。