华为OD机试真题——素数之积RSA加密算法（2025A卷：100分）Java/python/JavaScript/C/C++/GO最佳实现

2025 A卷 100分 题型

本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；

并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；

本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》

华为OD机试真题《素数之积RSA加密算法》：

---

文章快捷目录

题目描述及说明

Java

python

JavaScript

C

GO

更多内容

---

题目名称：素数之积RSA加密算法

---

知识点：数论、因数分解、素数判断
时间限制：1秒
空间限制：256MB
限定语言：不限

---

题目描述

RSA加密算法在网络安全中广泛应用，其安全性基于极大整数因数分解的困难性。给定一个32位正整数 num，请对其进行因数分解，找出两个素数，使得它们的乘积等于 num。若存在这样的素数对，则按升序输出这两个素数；否则输出 -1 -1。

输入描述

• 一个正整数 num，满足 0 < num < 2147483647。

输出描述

• 若分解成功，输出两个素数，以空格分隔并按升序排列；否则输出 -1 -1。

示例
输入：

15  

输出：

3 5  

说明：
15可以分解为素数3和5的乘积。

输入：

27  

输出：

-1 -1  

说明：
27的因数分解结果为3×3×3，不符合两个素数的要求。

输入约束

• 输入的数值保证唯一性，且至少存在一个有效解或无解。

---

Java

问题分析

给定一个32位正整数num，要求分解成两个素数的乘积。如果存在这样的两个素数，按升序输出；否则输出-1 -1。关键在于高效地找到这两个素数。

解题思路

1. 因数遍历：从2开始遍历到sqrt(num)，寻找num的因数。一旦找到因数i，对应的另一个因数为j=num/i。
2. 素数判断：对于找到的因数i和j，需要检查它们是否都是素数。
3. 优化遍历：先处理2的情况，然后遍历奇数以减少循环次数。
4. 高效素数判断：通过预检查小素数和6k±1的因数，减少不必要的计算。

代码实现

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int num = scanner.nextInt();// 检查因数2的情况if (num % 2 == 0) {int j = num / 2;if (isPrime(2) && isPrime(j)) {System.out.println("2 " + j);return;}}// 遍历奇数因数，从3开始for (int i = 3; i * i <= num; i += 2) {if (num % i == 0) {int j = num / i;if (isPrime(i) && isPrime(j)) {System.out.println(i + " " + j);return;}}}// 未找到符合条件的素数对System.out.println("-1 -1");}// 高效的素数判断函数private static boolean isPrime(int n) {if (n <= 1) return false;if (n <= 3) return true;if (n % 2 == 0 || n % 3 == 0) return false;// 检查6k ± 1的因数for (int i = 5; i * i <= n; i += 6) {if (n % i == 0 || n % (i + 2) == 0) {return false;}}return true;}
}

代码详解

1. 输入读取：使用Scanner读取输入的整数num。
2. 处理因数2：单独检查num是否能被2整除，以减少后续遍历次数。
3. 遍历奇数因数：从3开始，每次增加2，只检查奇数作为可能的因数。
4. 因数判断：对于每个i，检查是否是num的因数，并计算对应的j。
5. 素数判断：调用isPrime函数检查i和j是否都是素数，若是则输出结果并返回。
6. 未找到处理：循环结束后未找到则输出-1 -1。
7. isPrime函数：通过预检查2、3和6k±1的因数，高效判断素数。

示例测试

1. 输入15：

   • 因数i=3，j=5，均为素数，输出3 5。

2. 输入27：

   • 因数i=3，j=9，但9非素数；遍历结束未找到，输出-1 -1。

3. 输入25：

   • 因数i=5，j=5，均为素数，输出5 5。

综合分析

该方案通过优化因数遍历和素数判断，确保了高效性和正确性：

• 时间复杂度：最坏情况下O(sqrt(n))，由于减少遍历次数，实际效率更高。
• 空间复杂度：O(1)，无额外存储。
• 正确性：覆盖所有可能的因数组合，包括平方数和边界情况。
• 优化点：优先处理偶数和奇数遍历，结合高效素数判断，适合处理大数范围。

---

python

问题分析

给定一个正整数 num，要求将其分解为两个素数的乘积。如果存在这样的两个素数，按升序输出；否则输出 -1 -1。关键在于高效地找到这两个素数。

解题思路

1. 因数遍历：从 2 开始遍历到 sqrt(num)，寻找 num 的因数。找到因数 i 后，另一个因数为 j = num // i。
2. 素数判断：对于找到的因数 i 和 j，检查它们是否都是素数。
3. 优化遍历：先处理 2 的情况，然后遍历奇数以减少循环次数。
4. 高效素数判断：通过预检查 2、3 和 6k±1 的因数，减少不必要的计算。

代码实现

def is_prime(n):"""判断一个数是否为素数"""if n <= 1:return Falseif n <= 3:return Trueif n % 2 == 0 or n % 3 == 0:return Falsei = 5while i * i <= n:if n % i == 0 or n % (i + 2) == 0:return Falsei += 6return Truenum = int(input())# 先检查是否为偶数
if num % 2 == 0:j = num // 2if is_prime(j):print(2, j)exit()# 遍历奇数因数，从3开始到sqrt(num)
max_factor = int(num ** 0.5) + 1
for i in range(3, max_factor, 2):if num % i == 0:j = num // iif is_prime(i) and is_prime(j):print(i, j)exit()# 未找到符合条件的因数对
print(-1, -1)

代码详解

1. is_prime 函数：

   • 第 1-2 行：处理小于等于 1 的非素数情况。
   • 第 3-4 行：直接返回 True 当 n 是 2 或 3。
   • 第 5-6 行：快速排除能被 2 或 3 整除的数。
   • 第 7-11 行：检查 6k±1 形式的因数，减少循环次数。

2. 主逻辑部分：

   • 第 14 行：读取输入的正整数 num。
   • 第 17-20 行：检查 num 是否为偶数。如果是，计算另一个因数 j，若 j 是素数则直接输出结果。
   • 第 23-27 行：遍历奇数因数 i，检查是否能整除 num，并验证 i 和 j 是否均为素数。
   • 第 30 行：若未找到符合条件的因数对，输出 -1 -1。

示例测试

1. 输入 15：

   • 15 是奇数，检查 i=3，j=5。两者均为素数，输出 3 5。

2. 输入 27：

   • 27 是奇数，遍历到 i=3，j=9。9 不是素数，继续遍历无结果，最终输出 -1 -1。

3. 输入 25：

   • 25 是奇数，遍历到 i=5，j=5。两者均为素数，输出 5 5。

综合分析

该方案通过以下优化确保高效性：

• 因数遍历优化：先处理偶数，然后只遍历奇数，减少循环次数。
• 素数判断优化：利用 6k±1 规律，快速排除非素数。
• 时间复杂度：最坏情况下为 O(sqrt(n))，适用于 32 位整数范围。
• 空间复杂度：O(1)，无需额外存储空间。

该实现能正确处理所有边界情况，如质数输入、平方数等，确保结果正确且高效。

---

JavaScript

问题分析

给定一个正整数 num，要求将其分解为两个素数的乘积。若存在这样的素数对，按升序输出；否则输出 -1 -1。关键在于高效地找到这两个素数。

解题思路

1. 因数遍历：从 2 开始遍历到 Math.sqrt(num)，寻找 num 的因数。找到因数 i 后，另一个因数为 j = num / i。
2. 素数判断：对于找到的因数 i 和 j，检查它们是否都是素数。
3. 优化遍历：先处理 2 的情况，然后遍历奇数以减少循环次数。
4. 高效素数判断：通过预检查 2、3 和 6k±1 的因数，减少不必要的计算。

---

代码实现

const fs = require('fs');
const num = parseInt(fs.readFileSync(0).toString().trim());function isPrime(n) {if (n <= 1) return false;if (n <= 3) return true; // 2和3是素数if (n % 2 === 0 || n % 3 === 0) return false; // 排除2和3的倍数// 检查6k±1形式的因数，i从5开始，每次增加6for (let i = 5; i * i <= n; i += 6) {if (n % i === 0 || n % (i + 2) === 0) return false;}return true;
}// 处理偶数的特殊情况
if (num % 2 === 0) {const j = num / 2;if (isPrime(j)) {console.log(`2 ${j}`);process.exit();}
}// 遍历奇数因数，从3开始到sqrt(num)
for (let i = 3; i * i <= num; i += 2) {if (num % i === 0) {const j = num / i;if (isPrime(i) && isPrime(j)) {console.log(`${i} ${j}`);process.exit();}}
}// 未找到符合条件的素数对
console.log('-1 -1');

---

代码详解

1. 输入处理：

   const num = parseInt(fs.readFileSync(0).toString().trim());
   

   从标准输入读取内容并转换为整数 num。

2. isPrime 函数：

   • 第2行：若 n ≤ 1，直接返回 false（非素数）。
   • 第3行：若 n 是 2 或 3，返回 true。
   • 第4行：若 n 能被 2 或 3 整除，返回 false。
   • 第6-8行：检查 6k±1 形式的因数（如5、7、11、13等），快速排除非素数。

3. 处理偶数情况：

   if (num % 2 === 0) {const j = num / 2;if (isPrime(j)) {console.log(`2 ${j}`);process.exit();}
   }
   

   • 若 num 是偶数，则其中一个因数必为 2，另一个因数为 j = num / 2。
   • 检查 j 是否为素数，若是则输出并结束程序。

4. 遍历奇数因数：

   for (let i = 3; i * i <= num; i += 2) {if (num % i === 0) {const j = num / i;if (isPrime(i) && isPrime(j)) {console.log(`${i} ${j}`);process.exit();}}
   }
   

   • 从 3 开始，每次增加 2，遍历所有奇数。
   • 若 i 是 num 的因数，计算 j = num / i，并检查 i 和 j 是否均为素数。

5. 未找到时的输出：

   console.log('-1 -1');
   

   若遍历结束未找到符合条件的素数对，输出 -1 -1。

---

示例测试

1. 输入 15：

   • num = 15 是奇数，检查 i = 3，j = 5。
   • isPrime(3) 和 isPrime(5) 均为 true，输出 3 5。

2. 输入 27：

   • num = 27 是奇数，检查 i = 3，j = 9（9 不是素数）。
   • 继续遍历其他奇数，未找到符合条件的因数对，最终输出 -1 -1。

3. 输入 25：

   • num = 25 是奇数，检查 i = 5，j = 5。
   • isPrime(5) 为 true，输出 5 5。

---

综合分析

1. 时间复杂度：

   • 最坏情况：遍历到 sqrt(num)，时间复杂度为 O(sqrt(n))。
   • 素数判断：通过 6k±1 优化，将判断复杂度降至 O(sqrt(n)/6)。

2. 空间复杂度：O(1)，无额外存储空间。

3. 优化点：

   • 优先处理偶数：快速处理 2 的因数。
   • 仅遍历奇数：减少遍历次数。
   • 高效素数判断：利用 6k±1 规律减少循环次数。

4. 适用场景：

   • 适用于 32 位整数范围内的数值（最大约 2^31-1）。
   • 正确处理边界情况（如 num 为平方数或小素数）。

---

C++

问题分析

给定一个32位正整数 num，要求将其分解为两个素数的乘积。如果存在这样的两个素数，按升序输出；否则输出 -1 -1。关键在于高效地找到这两个素数。

---

解题思路

1. 因数遍历：从 2 开始遍历到 sqrt(num)，寻找 num 的因数。找到因数 i 后，另一个因数为 j = num / i。
2. 素数判断：对于找到的因数 i 和 j，检查它们是否都是素数。
3. 优化遍历：先处理 2 的情况，然后遍历奇数以减少循环次数。
4. 高效素数判断：通过预检查 2、3 和 6k±1 的因数，减少不必要的计算。

---

代码实现

#include <iostream>
using namespace std;bool isPrime(int n) {if (n <= 1) return false;    // 非正数不是素数if (n <= 3) return true;      // 2和3是素数if (n % 2 == 0 || n % 3 == 0) return false; // 排除2和3的倍数// 检查6k±1形式的因数for (long long i = 5; i * i <= n; i += 6) {if (n % i == 0 || n % (i + 2) == 0)return false;}return true;
}int main() {int num;cin >> num;// 处理偶数情况if (num % 2 == 0) {int j = num / 2;if (isPrime(j)) {cout << "2 " << j << endl;return 0;}}// 遍历奇数因数，从3到sqrt(num)for (long long i = 3; i * i <= num; i += 2) {if (num % i == 0) {int j = num / i;if (isPrime(i) && isPrime(j)) {cout << i << " " << j << endl;return 0;}}}// 未找到符合条件的素数对cout << "-1 -1" << endl;return 0;
}

---

代码详解

1. isPrime 函数：

   • 第3行：若 n ≤ 1，直接返回 false（非素数）。
   • 第4行：若 n 是 2 或 3，返回 true。
   • 第5行：若 n 能被 2 或 3 整除，返回 false。
   • 第8-10行：检查 6k±1 形式的因数（如5、7、11、13等），快速排除非素数。

2. 主函数逻辑：

   • 第15行：读取输入的正整数 num。
   • 第18-22行：检查 num 是否为偶数。如果是，计算另一个因数 j，若 j 是素数则直接输出结果。
   • 第25-32行：遍历奇数因数 i，检查是否能整除 num，并验证 i 和 j 是否均为素数。
   • 第35行：若未找到符合条件的因数对，输出 -1 -1。

---

示例测试

1. 输入 15：

   • num = 15 是奇数，检查 i = 3，j = 5。
   • isPrime(3) 和 isPrime(5) 均为 true，输出 3 5。

2. 输入 27：

   • num = 27 是奇数，检查 i = 3，j = 9（9 不是素数）。
   • 继续遍历其他奇数，未找到符合条件的因数对，最终输出 -1 -1。

3. 输入 25：

   • num = 25 是奇数，检查 i = 5，j = 5。
   • isPrime(5) 为 true，输出 5 5。

---

综合分析

1. 时间复杂度：

   • 最坏情况：遍历到 sqrt(num)，时间复杂度为 O(sqrt(n))。
   • 素数判断：通过 6k±1 优化，将判断复杂度降至 O(sqrt(n)/6)。

2. 空间复杂度：O(1)，无额外存储空间。

3. 优化点：

   • 优先处理偶数：快速处理 2 的因数。
   • 仅遍历奇数：减少遍历次数。
   • 高效素数判断：利用 6k±1 规律减少循环次数。

4. 适用场景：

   • 适用于 32 位整数范围内的数值（最大约 2^31-1）。
   • 正确处理边界情况（如 num 为平方数或小素数）。

---

C

问题分析

给定一个32位正整数 num，要求将其分解为两个素数的乘积。若存在这样的素数对，按升序输出；否则输出 -1 -1。关键在于高效地找到这两个素数。

解题思路

1. 因数遍历：从 2 开始遍历到 sqrt(num)，寻找 num 的因数。找到因数 i 后，另一个因数为 j = num / i。
2. 素数判断：对于找到的因数 i 和 j，检查它们是否都是素数。
3. 优化遍历：先处理 2 的情况，然后遍历奇数以减少循环次数。
4. 高效素数判断：通过预检查 2、3 和 6k±1 的因数，减少不必要的计算。

---

代码实现

#include <stdio.h>
#include <stdbool.h>bool is_prime(int n) {if (n <= 1) return false;if (n <= 3) return true;       // 2和3是素数if (n % 2 == 0 || n % 3 == 0)  // 排除2和3的倍数return false;// 检查6k±1形式的因数for (int i = 5; i * i <= n; i += 6) {if (n % i == 0 || n % (i + 2) == 0)return false;}return true;
}int main() {int num;scanf("%d", &num);// 处理偶数情况if (num % 2 == 0) {int j = num / 2;if (is_prime(j)) {printf("2 %d\n", j);return 0;}}// 遍历奇数因数，从3开始到sqrt(num)for (long i = 3; i * i <= num; i += 2) {if (num % i == 0) {int j = num / i;if (is_prime(i) && is_prime(j)) {printf("%ld %d\n", i, j);return 0;}}}// 未找到符合条件的因数对printf("-1 -1\n");return 0;
}

---

代码详解

1. is_prime 函数：

   • 第4行：若 n ≤ 1，返回 false（非素数）。
   • 第5行：若 n 是 2 或 3，返回 true。
   • 第6-7行：若 n 能被 2 或 3 整除，返回 false。
   • 第9-12行：检查 6k±1 形式的因数（如5、7、11、13等），快速排除非素数。

2. 主函数逻辑：

   • 第17行：读取输入的整数 num。
   • 第20-24行：若 num 是偶数，检查 num/2 是否为素数。若是，输出 2 和 num/2。
   • 第27-34行：遍历奇数因数 i，检查是否能整除 num，并验证 i 和 j 是否均为素数。
   • 第37行：若未找到符合条件的因数对，输出 -1 -1。

---

示例测试

1. 输入15：

   • num = 15 是奇数，检查 i = 3，j = 5。两者均为素数，输出 3 5。

2. 输入27：

   • num = 27 是奇数，检查 i = 3，j = 9。9 不是素数，最终输出 -1 -1。

3. 输入25：

   • num = 25 是奇数，检查 i = 5，j = 5。两者均为素数，输出 5 5。

---

综合分析

1. 时间复杂度：

   • 最坏情况：遍历到 sqrt(num)，时间复杂度为 O(sqrt(n))。
   • 素数判断：通过 6k±1 优化，将判断复杂度降至 O(sqrt(n)/6)。

2. 空间复杂度：O(1)，无额外存储空间。

3. 优化点：

   • 优先处理偶数：快速处理 2 的因数。
   • 仅遍历奇数：减少循环次数。
   • 高效素数判断：利用 6k±1 规律减少循环次数。

4. 适用场景：

   • 适用于 32 位整数范围内的数值（最大约 2^31-1）。
   • 正确处理边界情况（如 num 为平方数或小素数）。

---

GO

问题分析

给定一个32位正整数 num，要求将其分解为两个素数的乘积。若存在这样的素数对，按升序输出；否则输出 -1 -1。关键在于高效地找到这两个素数。

---

解题思路

1. 因数遍历：从 2 开始遍历到 sqrt(num)，寻找 num 的因数。找到因数 i 后，另一个因数为 j = num / i。
2. 素数判断：对于找到的因数 i 和 j，检查它们是否都是素数。
3. 优化遍历：先处理 2 的情况，然后遍历奇数以减少循环次数。
4. 高效素数判断：通过预检查 2、3 和 6k±1 的因数，减少不必要的计算。

---

代码实现

package mainimport ("fmt""math"
)func isPrime(n int) bool {if n <= 1 {return false}if n <= 3 { // 2和3是素数return true}if n%2 == 0 || n%3 == 0 { // 排除2和3的倍数return false}// 检查6k±1形式的因数for i := 5; i*i <= n; i += 6 {if n%i == 0 || n%(i+2) == 0 {return false}}return true
}func main() {var num intfmt.Scan(&num)// 处理偶数情况if num%2 == 0 {j := num / 2if isPrime(j) {fmt.Printf("2 %d\n", j)return}}// 遍历奇数因数，从3到sqrt(num)maxFactor := int(math.Sqrt(float64(num))) + 1for i := 3; i <= maxFactor; i += 2 {if num%i == 0 {j := num / iif isPrime(i) && isPrime(j) {fmt.Printf("%d %d\n", i, j)return}}}// 未找到符合条件的因数对fmt.Println("-1 -1")
}

---

代码详解

1. isPrime 函数：

   • 第8-10行：若 n ≤ 1，返回 false（非素数）。
   • 第11-13行：若 n 是 2 或 3，返回 true。
   • 第14-16行：若 n 能被 2 或 3 整除，返回 false。
   • 第18-21行：检查 6k±1 形式的因数（如5、7、11、13等），快速排除非素数。

2. 主函数逻辑：

   • 第26行：读取输入的整数 num。
   • 第29-33行：若 num 是偶数，检查 num/2 是否为素数。若是，输出 2 和 num/2。
   • 第36-44行：遍历奇数因数 i，检查是否能整除 num，并验证 i 和 j 是否均为素数。
   • 第47行：若未找到符合条件的因数对，输出 -1 -1。

---

示例测试

1. 输入15：

   • num = 15 是奇数，检查 i = 3，j = 5。两者均为素数，输出 3 5。

2. 输入27：

   • num = 27 是奇数，检查 i = 3，j = 9。9 不是素数，最终输出 -1 -1。

3. 输入25：

   • num = 25 是奇数，检查 i = 5，j = 5。两者均为素数，输出 5 5。

---

综合分析

1. 时间复杂度：

   • 最坏情况：遍历到 sqrt(num)，时间复杂度为 O(sqrt(n))。
   • 素数判断：通过 6k±1 优化，将判断复杂度降至 O(sqrt(n)/6)。

2. 空间复杂度：O(1)，无额外存储空间。

3. 优化点：

   • 优先处理偶数：快速处理 2 的因数。
   • 仅遍历奇数：减少循环次数。
   • 高效素数判断：利用 6k±1 规律减少循环次数。

4. 适用场景：

   • 适用于 32 位整数范围内的数值（最大约 2^31-1）。
   • 正确处理边界情况（如 num 为平方数或小素数）。

---

更多内容：

https://www.kdocs.cn/l/cvk0eoGYucWA

本文发表于【纪元A梦】，关注我，获取更多实用教程/资源！