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 は値渡しなので、関数の中で割っていっても呼び出し側の変数は変わりません。