華為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。

示例
輸入：

輸出：

3 5

說明：
15可以分解為素數3和5的乘積。

輸入：

輸出：

-1 -1

說明：
27的因數分解結果為3×3×3，不符合兩個素數的要求。

輸入約束

輸入的數值保證唯一性，且至少存在一個有效解或無解。

Java

問題分析

給定一個32位正整數num，要求分解成兩個素數的乘積。如果存在這樣的兩個素數，按升序輸出；否則輸出-1 -1。關鍵在于高效地找到這兩個素數。

解題思路

因數遍歷：從2開始遍歷到sqrt(num)，尋找num的因數。一旦找到因數i，對應的另一個因數為j=num/i。
素數判斷：對于找到的因數i和j，需要檢查它們是否都是素數。
優化遍歷：先處理2的情況，然后遍歷奇數以減少循環次數。
高效素數判斷：通過預檢查小素數和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;}
}

代碼詳解

輸入讀取：使用Scanner讀取輸入的整數num。
處理因數2：單獨檢查num是否能被2整除，以減少后續遍歷次數。
遍歷奇數因數：從3開始，每次增加2，只檢查奇數作為可能的因數。
因數判斷：對于每個i，檢查是否是num的因數，并計算對應的j。
素數判斷：調用isPrime函數檢查i和j是否都是素數，若是則輸出結果并返回。
未找到處理：循環結束后未找到則輸出-1 -1。
isPrime函數：通過預檢查2、3和6k±1的因數，高效判斷素數。

示例測試

輸入15：
- 因數i=3，j=5，均為素數，輸出3 5。
輸入27：
- 因數i=3，j=9，但9非素數；遍歷結束未找到，輸出-1 -1。
輸入25：
- 因數i=5，j=5，均為素數，輸出5 5。

綜合分析

該方案通過優化因數遍歷和素數判斷，確保了高效性和正確性：

時間復雜度：最壞情況下O(sqrt(n))，由于減少遍歷次數，實際效率更高。
空間復雜度：O(1)，無額外存儲。
正確性：覆蓋所有可能的因數組合，包括平方數和邊界情況。
優化點：優先處理偶數和奇數遍歷，結合高效素數判斷，適合處理大數范圍。

python

問題分析

給定一個正整數 num，要求將其分解為兩個素數的乘積。如果存在這樣的兩個素數，按升序輸出；否則輸出 -1 -1。關鍵在于高效地找到這兩個素數。

解題思路

因數遍歷：從 2 開始遍歷到 sqrt(num)，尋找 num 的因數。找到因數 i 后，另一個因數為 j = num // i。
素數判斷：對于找到的因數 i 和 j，檢查它們是否都是素數。
優化遍歷：先處理 2 的情況，然后遍歷奇數以減少循環次數。
高效素數判斷：通過預檢查 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)

代碼詳解

is_prime 函數：
- 第 1-2 行：處理小于等于 1 的非素數情況。
- 第 3-4 行：直接返回 True 當 n 是 2 或 3。
- 第 5-6 行：快速排除能被 2 或 3 整除的數。
- 第 7-11 行：檢查 6k±1 形式的因數，減少循環次數。
主邏輯部分：
- 第 14 行：讀取輸入的正整數 num。
- 第 17-20 行：檢查 num 是否為偶數。如果是，計算另一個因數 j，若 j 是素數則直接輸出結果。
- 第 23-27 行：遍歷奇數因數 i，檢查是否能整除 num，并驗證 i 和 j 是否均為素數。
- 第 30 行：若未找到符合條件的因數對，輸出 -1 -1。

示例測試

輸入 15：
- 15 是奇數，檢查 i=3，j=5。兩者均為素數，輸出 3 5。
輸入 27：
- 27 是奇數，遍歷到 i=3，j=9。9 不是素數，繼續遍歷無結果，最終輸出 -1 -1。
輸入 25：
- 25 是奇數，遍歷到 i=5，j=5。兩者均為素數，輸出 5 5。

綜合分析

該方案通過以下優化確保高效性：

因數遍歷優化：先處理偶數，然后只遍歷奇數，減少循環次數。
素數判斷優化：利用 6k±1 規律，快速排除非素數。
時間復雜度：最壞情況下為 O(sqrt(n))，適用于 32 位整數范圍。
空間復雜度：O(1)，無需額外存儲空間。

該實現能正確處理所有邊界情況，如質數輸入、平方數等，確保結果正確且高效。

JavaScript

問題分析

給定一個正整數 num，要求將其分解為兩個素數的乘積。若存在這樣的素數對，按升序輸出；否則輸出 -1 -1。關鍵在于高效地找到這兩個素數。

解題思路

因數遍歷：從 2 開始遍歷到 Math.sqrt(num)，尋找 num 的因數。找到因數 i 后，另一個因數為 j = num / i。
素數判斷：對于找到的因數 i 和 j，檢查它們是否都是素數。
優化遍歷：先處理 2 的情況，然后遍歷奇數以減少循環次數。
高效素數判斷：通過預檢查 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');

代碼詳解

輸入處理：
```
const num = parseInt(fs.readFileSync(0).toString().trim());
```
從標準輸入讀取內容并轉換為整數 num。
isPrime 函數：
- 第2行：若 n ≤ 1，直接返回 false（非素數）。
- 第3行：若 n 是 2 或 3，返回 true。
- 第4行：若 n 能被 2 或 3 整除，返回 false。
- 第6-8行：檢查 6k±1 形式的因數（如5、7、11、13等），快速排除非素數。
處理偶數情況：
```
if (num % 2 === 0) {const j = num / 2;if (isPrime(j)) {console.log(`2 ${j}`);process.exit();}
}
```
- 若 num 是偶數，則其中一個因數必為 2，另一個因數為 j = num / 2。
- 檢查 j 是否為素數，若是則輸出并結束程序。

遍歷奇數因數：

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 是否均為素數。

未找到時的輸出：
```
console.log('-1 -1');
```
若遍歷結束未找到符合條件的素數對，輸出 -1 -1。

示例測試

輸入 15：
- num = 15 是奇數，檢查 i = 3，j = 5。
- isPrime(3) 和 isPrime(5) 均為 true，輸出 3 5。
輸入 27：
- num = 27 是奇數，檢查 i = 3，j = 9（9 不是素數）。
- 繼續遍歷其他奇數，未找到符合條件的因數對，最終輸出 -1 -1。
輸入 25：
- num = 25 是奇數，檢查 i = 5，j = 5。
- isPrime(5) 為 true，輸出 5 5。

綜合分析

時間復雜度：
- 最壞情況：遍歷到 sqrt(num)，時間復雜度為 O(sqrt(n))。
- 素數判斷：通過 6k±1 優化，將判斷復雜度降至 O(sqrt(n)/6)。
空間復雜度：O(1)，無額外存儲空間。
優化點：
- 優先處理偶數：快速處理 2 的因數。
- 僅遍歷奇數：減少遍歷次數。
- 高效素數判斷：利用 6k±1 規律減少循環次數。
適用場景：
- 適用于 32 位整數范圍內的數值（最大約 2^31-1）。
- 正確處理邊界情況（如 num 為平方數或小素數）。

C++

問題分析

給定一個32位正整數 num，要求將其分解為兩個素數的乘積。如果存在這樣的兩個素數，按升序輸出；否則輸出 -1 -1。關鍵在于高效地找到這兩個素數。

解題思路

因數遍歷：從 2 開始遍歷到 sqrt(num)，尋找 num 的因數。找到因數 i 后，另一個因數為 j = num / i。
素數判斷：對于找到的因數 i 和 j，檢查它們是否都是素數。
優化遍歷：先處理 2 的情況，然后遍歷奇數以減少循環次數。
高效素數判斷：通過預檢查 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;
}

代碼詳解

isPrime 函數：
- 第3行：若 n ≤ 1，直接返回 false（非素數）。
- 第4行：若 n 是 2 或 3，返回 true。
- 第5行：若 n 能被 2 或 3 整除，返回 false。
- 第8-10行：檢查 6k±1 形式的因數（如5、7、11、13等），快速排除非素數。
主函數邏輯：
- 第15行：讀取輸入的正整數 num。
- 第18-22行：檢查 num 是否為偶數。如果是，計算另一個因數 j，若 j 是素數則直接輸出結果。
- 第25-32行：遍歷奇數因數 i，檢查是否能整除 num，并驗證 i 和 j 是否均為素數。
- 第35行：若未找到符合條件的因數對，輸出 -1 -1。

示例測試

輸入 15：
- num = 15 是奇數，檢查 i = 3，j = 5。
- isPrime(3) 和 isPrime(5) 均為 true，輸出 3 5。
輸入 27：
- num = 27 是奇數，檢查 i = 3，j = 9（9 不是素數）。
- 繼續遍歷其他奇數，未找到符合條件的因數對，最終輸出 -1 -1。
輸入 25：
- num = 25 是奇數，檢查 i = 5，j = 5。
- isPrime(5) 為 true，輸出 5 5。

綜合分析

時間復雜度：
- 最壞情況：遍歷到 sqrt(num)，時間復雜度為 O(sqrt(n))。
- 素數判斷：通過 6k±1 優化，將判斷復雜度降至 O(sqrt(n)/6)。
空間復雜度：O(1)，無額外存儲空間。
優化點：
- 優先處理偶數：快速處理 2 的因數。
- 僅遍歷奇數：減少遍歷次數。
- 高效素數判斷：利用 6k±1 規律減少循環次數。
適用場景：
- 適用于 32 位整數范圍內的數值（最大約 2^31-1）。
- 正確處理邊界情況（如 num 為平方數或小素數）。

C

問題分析

給定一個32位正整數 num，要求將其分解為兩個素數的乘積。若存在這樣的素數對，按升序輸出；否則輸出 -1 -1。關鍵在于高效地找到這兩個素數。

解題思路

因數遍歷：從 2 開始遍歷到 sqrt(num)，尋找 num 的因數。找到因數 i 后，另一個因數為 j = num / i。
素數判斷：對于找到的因數 i 和 j，檢查它們是否都是素數。
優化遍歷：先處理 2 的情況，然后遍歷奇數以減少循環次數。
高效素數判斷：通過預檢查 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;
}

代碼詳解

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等），快速排除非素數。
主函數邏輯：
- 第17行：讀取輸入的整數 num。
- 第20-24行：若 num 是偶數，檢查 num/2 是否為素數。若是，輸出 2 和 num/2。
- 第27-34行：遍歷奇數因數 i，檢查是否能整除 num，并驗證 i 和 j 是否均為素數。
- 第37行：若未找到符合條件的因數對，輸出 -1 -1。

示例測試

輸入15：
- num = 15 是奇數，檢查 i = 3，j = 5。兩者均為素數，輸出 3 5。
輸入27：
- num = 27 是奇數，檢查 i = 3，j = 9。9 不是素數，最終輸出 -1 -1。
輸入25：
- num = 25 是奇數，檢查 i = 5，j = 5。兩者均為素數，輸出 5 5。

綜合分析

時間復雜度：
- 最壞情況：遍歷到 sqrt(num)，時間復雜度為 O(sqrt(n))。
- 素數判斷：通過 6k±1 優化，將判斷復雜度降至 O(sqrt(n)/6)。
空間復雜度：O(1)，無額外存儲空間。
優化點：
- 優先處理偶數：快速處理 2 的因數。
- 僅遍歷奇數：減少循環次數。
- 高效素數判斷：利用 6k±1 規律減少循環次數。
適用場景：
- 適用于 32 位整數范圍內的數值（最大約 2^31-1）。
- 正確處理邊界情況（如 num 為平方數或小素數）。

GO

問題分析

給定一個32位正整數 num，要求將其分解為兩個素數的乘積。若存在這樣的素數對，按升序輸出；否則輸出 -1 -1。關鍵在于高效地找到這兩個素數。

解題思路

因數遍歷：從 2 開始遍歷到 sqrt(num)，尋找 num 的因數。找到因數 i 后，另一個因數為 j = num / i。
素數判斷：對于找到的因數 i 和 j，檢查它們是否都是素數。
優化遍歷：先處理 2 的情況，然后遍歷奇數以減少循環次數。
高效素數判斷：通過預檢查 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")
}

代碼詳解

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等），快速排除非素數。
主函數邏輯：
- 第26行：讀取輸入的整數 num。
- 第29-33行：若 num 是偶數，檢查 num/2 是否為素數。若是，輸出 2 和 num/2。
- 第36-44行：遍歷奇數因數 i，檢查是否能整除 num，并驗證 i 和 j 是否均為素數。
- 第47行：若未找到符合條件的因數對，輸出 -1 -1。

示例測試

輸入15：
- num = 15 是奇數，檢查 i = 3，j = 5。兩者均為素數，輸出 3 5。
輸入27：
- num = 27 是奇數，檢查 i = 3，j = 9。9 不是素數，最終輸出 -1 -1。
輸入25：
- num = 25 是奇數，檢查 i = 5，j = 5。兩者均為素數，輸出 5 5。

綜合分析

時間復雜度：
- 最壞情況：遍歷到 sqrt(num)，時間復雜度為 O(sqrt(n))。
- 素數判斷：通過 6k±1 優化，將判斷復雜度降至 O(sqrt(n)/6)。
空間復雜度：O(1)，無額外存儲空間。
優化點：
- 優先處理偶數：快速處理 2 的因數。
- 僅遍歷奇數：減少循環次數。
- 高效素數判斷：利用 6k±1 規律減少循環次數。
適用場景：
- 適用于 32 位整數范圍內的數值（最大約 2^31-1）。
- 正確處理邊界情況（如 num 為平方數或小素數）。