P2528. 素数之积

解题思路

经典的大数分解问题。 关于素数相关的内容，可以详看 算法题中常用数学概念、公式、方法汇总 里的相关部分。

暴力解

比较容易想到的暴力解法包含以下步骤：

1. 从小到大枚举所有小于 sqrt(num) 的数 a。 2. 判断 num 是否可以整除 a：

• 若不可以，则直接跳过，遍历下一个 a。
• 若可以，则进行后续判断：
• 判断 a 是否是素数：
• 若不是，则直接跳过，遍历下一个 a。
• 若是，则进行后续判断：
• 判断 b = num // a 是否是素数：
• 若不是，则直接跳过，遍历下一个 a。
• 若是，则 a、b 为答案。

上述过程慢的原因主要在于，计算 a 或 b 是否是素数的环节。 可以使用质数筛来优化上述过程。

质数筛

使用质数筛解决上述大数分解的过程如下：

1. 构建长度为 num + 1 的质数筛数组 sieve。 sieve[i] 是 True 表示 i 是质数，sieve[i] 是 False 表示 i 是合数。 2. 枚举质数筛中每一个质数 a，即 sieve[a] = True 的下标。 3. 判断 num 是否可以整除 a：

• 若不可以，则直接跳过，遍历下一个 a。
• 若可以，则进行后续判断：
• 判断 b = num // a 是否是素数：
• 若不是，则直接跳过，遍历下一个 a。
• 若是，则 a、b 为答案。

复杂度分析 设输入的数为 num。瓶颈在埃氏筛的构建：需要初始化长度为 num+1 的布尔数组，并对每个素数标记其所有倍数，时间复杂度为 O(num log log num)，空间复杂度为 O(num)。之后的枚举阶段，从小到大遍历所有素数 a，对每个 a 做一次整除判断，命中时用集合（Python 版 set，O(1) 查询）判断 b = num // a 是否为素数，这一段不超过 O(num)。整体时间由筛主导，为 O(num log log num)；num 越大，筛的内存与时间开销越明显，这是本算法的主要瓶颈。

边界与注意事项

• 找不到分解时输出 -1 -1：isFind 标记初始为 False，只有真正找到一对素数才置 True 并退出循环；例如 num 本身是素数，或 num 的素因子分解不是恰好两个素数相乘时，都会落到这个分支。
• 枚举按素数从小到大进行，且 b = num // a，所以命中时输出的一定是较小的素数在前。
• num 恰为某个素数的平方（如 49 = 7*7）也能被正确处理：此时 a 与 b 相等，两者都能通过素数判断。
• 筛中 0 和 1 被显式标记为非素数，保证它们不会被当成因子输出。