题目描述
RSA加密算法在网络安全世界中无处不在，它利用了极大整数因数分解的困难度，数据越大，安全系数越高。给定一个32位正整数，请对其进行因数分解，找出是哪两个素数的乘积。
输入输出要求
- 输入：一个正整数 num（0 < num <= 2147483647）
- 输出：如果成功找到，以单个空格分割，从小到大输出两个素数；分解失败，请输出
-1 -1
示例
示例1
- 输入：
15 - 输出：
3 5 - 说明：因数分解后，找到两个素数3和5，使得3*5=15，按从小到大排列后，输出3 5。
示例2
- 输入：
27 - 输出：
-1 -1 - 说明：通过因数分解，找不到任何素数，使得他们的乘积为27，输出-1 -1。
知识点补充
- 素数定义：如果一个数字不是素数，那它除了1和他本身一定还有别的约数。
- 优化搜索范围：如果一个数的约数在其开平方的右边，则必然会存在一个约数在其开平方的左边。
- 判断质数：判断一个数是否为质数，只需要观察在其 2 到 开平方数 中间是否含有约数即可。
- 例如：判断16是否为质数，我们去找16的约数时，判断它的范围只需要找到 \sqrt{16} 就可以了，而不必一直找到 <16 或者 <= 16/2。
优化后的Java解法
import java.util.Scanner;
/**
* RSA素数分解求解
* 寻找两个素数使其乘积等于给定的整数
* @since 2026-04
*/
public class ProductOfPrime {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
if (scanner.hasNextInt()) {
int num = scanner.nextInt();
solve(num);
}
scanner.close();
}
/**
* 核心求解逻辑
*/
private static void solve(int num) {
int a = -1;
int b = -1;
// 只需要遍历到 num 的平方根
// 因为如果 num = p * q，且 p <= q，那么 p 一定 <= sqrt(num)
int limit = (int) Math.sqrt(num);
for (int i = 2; i <= limit; i++) {
// 1. 判断 i 是否为素数
// 2. 判断 i 是否能整除 num
if (isPrime(i) && num % i == 0) {
int otherFactor = num / i;
// 3. 判断另一个因子是否也为素数
if (isPrime(otherFactor)) {
a = i;
b = otherFactor;
break; // 找到一组解后即可退出（题目隐含寻找一组解）
}
}
}
System.out.println(a + " " + b);
}
/**
* 判断是否是素数
* 时间复杂度: O(sqrt(n))
*
* @param arg 待判断的整数
* @return 如果是素数返回true，否则返回false
*/
public static boolean isPrime(int arg) {
if (arg <= 1) {
return false;
}
if (arg == 2) {
return true;
}
if (arg % 2 == 0) {
return false;
}
// 只需要判断到 sqrt(arg)
int sqrt = (int) Math.sqrt(arg);
for (int j = 3; j <= sqrt; j += 2) { // 从3开始，只判断奇数
if (arg % j == 0) {
return false;
}
}
return true;
}
}