给定正整数 n，求一个最长的序列 a0, a1, …, ak，满足每个 ai 1 且所有 ai 的乘积等于 n。请给出算法并分析复杂度。

Question

给定正整数 n，求一个最长的序列 a0, a1, …, ak，满足每个 ai > 1 且所有 ai 的乘积等于 n。请给出算法并分析复杂度。

Accepted Answer

考察点：考察整数分解与贪心/动态规划结合的算法设计能力。回答思路：理解乘积分解与序列长度的关系 优先分解出尽可能多的因子 正确处理剩余素因子 分析时间与空间复杂度

给定正整数 n，求一个最长的序列 a0, a1, …, ak，满足每个 ai > 1 且所有 ai 的乘积等于 n。请给出算法并分析复杂度。