language-agnostic - 如何获得k个素数？

Question

有没有一种算法可以取一个数 k，并返回一个数 j，使得 j 有 k 个素因数？注意：算法应该在多项式时间内运行。

假设您没有质数表。

Answer 1

显而易见的答案：从素数表开始，给定一个 number k，将k这些素数相乘并返回结果。假设k足够小以使乘法时间保持恒定，则应该以线性时间运行。

如果你需要计算找到素数的时间，它应该仍然是多项式时间，使用埃拉托色尼的筛子来找到素数表。