如何獲得k素因子？

Question

是否有一個算法可以採用數字k，並返回一個數字j使得j具有k個素數因子？注意：算法應該在多項式時間運行。

假設您沒有質數表。

Answer 1

顯而易見的答案：從素數表格開始，給定數字k，將這些質數乘以k並返回結果。假設k足夠小，乘法時間保持不變，那應該在線性時間內運行。

如果您需要計算查找質數的時間，它應該仍然是多項式時間，使用Erathosthenese篩子查找質數表。