华为OD机试 - RSA加密算法（Python/JS/C/C++ 2024 E卷 100分）
华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
RSA加密算法在网络安全世界中无处不在，它利用了极大整数因数分解的困难度，数据越大，安全系数越高。
给定一个32位正整数，请对其进行因数分解，找出是哪两个素数的乘积。
二、输入描述
一个正整数num
0 < num <= 2147483647
三、输出描述
如果成功找到，以单个空格分割，从小到大输出两个素数，分解失败，请输出-1 -1。
四、解题思路
- 遍历从2到floor(sqrt(num))的所有可能的因子i，检查是否i是num的因子，即num % i == 0。
- 对于每一个找到的因子i，计算另一个因子num / i，并验证这两个因子是否都是素数。
- 如果找到一对满足条件的素数因子，按照从小到大的顺序输出。如果没有找到，则输出-1 -1。
- 在找到第一对满足条件的素数因子后，立即终止循环，减少不必要的计算。
这种方法利用了数学上的因数分解和素数验证，确保了算法的高效性和准确性，适用于32位整数范围内的输入。
五、Python算法源码
import math
import sys
def is_prime(a):
"""
判断一个数是否为素数
:param a: 要判断的数
:return: 如果是素数返回True，否则返回False
"""
if a < 2:
return False
sqrt_a = int(math.floor(math.sqrt(a)))
for i in range(2, sqrt_a + 1):
if a % i == 0:
return False
return True
def main():
# 读取输入的num
input_line = sys.stdin.readline().strip()
if not input_line:
print("-1 -1")
return
num = int(input_line)
# 计算num的平方根n，取整数部分作为循环的终止条件
n = int(math.floor(math.sqrt(num)))
# 初始化结果为-1 -1
result = "-1 -1"
# 遍历从2到n，寻找因子
for i in range(2, n + 1):
# 如果num能被i整除，说明i是num的一个因子
if num % i == 0:
other_factor = num // i
# 检查i和num/i是否都是素数
if is_prime(i) and is_prime(other_factor):
# 确保输出顺序为从小到大
if i < other_factor:
result = f"{i} {other_factor}"
else:
result = f"{other_factor} {i}"
# 找到一对因子后，立即终止循环
break
# 输出结果
print(result)
if __name__ == "__main__":
main()
六、JavaScript算法源码
// 引入读取标准输入的模块
const readline = require('readline');
// 创建接口实例
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
// 存储输入的行
let inputLines = [];
// 读取每一行输入
rl.on('line', (line) => {
inputLines.push(line.trim());
// 只需要读取一行输入
if (inputLines.length === 1) {
rl.close();
}
});
// 当输入结束后处理数据
rl.on('close', () => {
// 读取输入的num
const num = parseInt(inputLines[0]);
// 函数：判断一个数是否为素数
function isPrime(a) {
if (a < 2) return false;
const sqrtA = Math.floor(Math.sqrt(a));
for (let i = 2; i <= sqrtA; i++) {
if (a % i === 0) return false;
}
return true;
}
// 计算num的平方根n，取整数部分作为循环的终止条件
const n = Math.floor(Math.sqrt(num));
// 初始化结果为-1 -1
let result = "-1 -1";
// 遍历从2到n，寻找因子
for (let i = 2; i <= n; i++) {
// 如果num能被i整除，说明i是num的一个因子
if (num % i === 0) {
const otherFactor = Math.floor(num / i);
// 检查i和num/i是否都是素数
if (isPrime(i) && isPrime(otherFactor)) {
// 确保输出顺序为从小到大
if (i < otherFactor) {
result = `${i} ${otherFactor}`;
} else {
result = `${otherFactor} ${i}`;
}
// 找到一对因子后，立即终止循环
break;
}
}
}
// 输出结果
console.log(result);
});
七、C算法源码
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
/**
* 判断一个数是否为素数
* @param a 要判断的数
* @return 如果是素数返回true，否则返回false
*/
bool isPrime(long a) {
if (a < 2) return false;
long sqrt_a = (long)floor(sqrt((double)a));
for (long i = 2; i <= sqrt_a; i++) {
if (a % i == 0) return false;
}
return true;
}
int main() {
long num;
// 读取输入的num
if (scanf("%ld", &num) != 1) {
printf("-1 -1\n");
return 0;
}
// 计算num的平方根n，取整数部分作为循环的终止条件
long n = (long)floor(sqrt((double)num));
// 初始化结果为-1 -1
char result[20] = "-1 -1";
// 遍历从2到n，寻找因子
for (long i = 2; i <= n; i++) {
// 如果num能被i整除，说明i是num的一个因子
if (num % i == 0) {
long otherFactor = num / i;
// 检查i和num/i是否都是素数
if (isPrime(i) && isPrime(otherFactor)) {
// 确保输出顺序为从小到大
if (i < otherFactor) {
sprintf(result, "%ld %ld", i, otherFactor);
} else {
sprintf(result, "%ld %ld", otherFactor, i);
}
// 找到一对因子后，立即终止循环
break;
}
}
}
// 输出结果
printf("%s\n", result);
return 0;
}
八、C++算法源码
#include <bits/stdc++.h>
using namespace std;
/**
* 判断一个数是否为素数
* @param a 要判断的数
* @return 如果是素数返回true，否则返回false
*/
bool isPrime(long a) {
if (a < 2) return false;
long sqrt_a = floor(sqrt((double)a));
for (long i = 2; i <= sqrt_a; i++) {
if (a % i == 0) return false;
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
long num;
// 读取输入的num
if(!(cin >> num)){
cout << "-1 -1\n";
return 0;
}
// 计算num的平方根n，取整数部分作为循环的终止条件
long n = floor(sqrt((double)num));
// 初始化结果为-1 -1
string result = "-1 -1";
// 遍历从2到n，寻找因子
for(long i = 2; i <= n; i++) {
// 如果num能被i整除，说明i是num的一个因子
if(num % i == 0){
long otherFactor = num / i;
// 检查i和num/i是否都是素数
if(isPrime(i) && isPrime(otherFactor)){
// 确保输出顺序为从小到大
if(i < otherFactor){
result = to_string(i) + " " + to_string(otherFactor);
}
else{
result = to_string(otherFactor) + " " + to_string(i);
}
// 找到一对因子后，立即终止循环
break;
}
}
}
// 输出结果
cout << result;
return 0;
}
🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）
🏆本文收录于，华为OD机试真题（Python/JS/C/C++）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
原文地址：https://blog.csdn.net/guorui_java/article/details/142980030
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！