language-agnostic - k個の素因数を取得するには?

Question

数値 k を取り、j が k 個の素因数を持つように数値 j を返すアルゴリズムはありますか? 注: アルゴリズムは多項式時間で実行する必要があります。

素数の表がないとします。

Answer 1

明白な答え: 素数の表から始めて、 number を指定すると、それらの素数をk掛け合わせて結果を返します。乗算時間が一定のままであるほど小さいkと仮定すると、線形時間で実行する必要があります。k

素数を見つけるために時間を数える必要がある場合でも、エラトステネスのふるいを使用して素数の表を見つける多項式時間である必要があります。