2024年华为OD机试真题-素数之积
华为OD机试真题-素数之积-2024年OD统一考试(D卷)
题目描述:
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
解题思路:
考察递归,使用循环判断数值范围解答。
JAVA解法:
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int num = scanner.nextInt(); scanner.close(); if (num <= 1) { System.out.println("-1 -1"); return; } int[] result = factorizeToPrimes(num); if (result[0] == -1) { System.out.println("-1 -1"); } else { System.out.println(result[0] + " " + result[1]); } } private static int[] factorizeToPrimes(int num) { for (int i = 2; i * i <= num; i++) { if (isPrime(i) && num % i == 0) { int other = num / i; if (isPrime(other)) { return new int[]{Math.min(i, other), Math.max(i, other)}; } } } return new int[]{-1, -1}; } private static boolean isPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; } }
Python解法:
import math def zs(n): if n<=1: return False for x in range(2,int(math.sqrt(n))+1): if n%x==0: return False return True n=int(input()) a,b=-1,-1 for i in range(2,int(math.sqrt(n))+1): if zs(i): if n%i==0 and zs(n/i): a=i b=int(n/i) print(str(a)+' '+str(b))
C++解法:
#include <iostream> using namespace std; #include<cmath> bool is_pr(int num) { bool res = true; for (int i = 2; i <= sqrt(num); i++) { if (num % i == 0) return false; } return res; } int main() { int num; cin >> num; bool f = false; for (int i = 2; i <= sqrt(num); i++) { if (num % i == 0 && is_pr(i)) { if (is_pr(num / i)) { cout << i << " " << num / i << endl; f = true; break; } } } if (!f) cout << -1 << " " << -1 << endl; return 0; }
欢迎交流指正~
#华为od##华为##华为OD##华为od机试#
华为OD机试题库2024年 文章被收录于专栏
2024年OD统一考试(D卷),最新最完整题库。 收录130+道真题,提供解题思路,Java/Python/C++三种答案源码。