素数之积 - 华为OD统一考试(D卷)

OD统一考试（D卷）

分值： 100分

题解： Java / Python / C++

题目描述

RSA加密算法只在网络安全世界中无处不在，它利用了极大整数因数分解的困难度，数据越大，安全系数越高，给定一个32 位正整，请对其进行因数分解，找出是哪两个素数的乘积。

输入描述

一个正整数num()

输出描述

如果成功找到，以单个空格分割，从小到大输出两个素数，分解失败，请输出-1,-1

示例1

输入：
15

输出：
3 5

示例2

输入：
27

输出：
-1 -1

题解

这道题目是一个简单的数学题。

解题思路

1. 编写一个函数来判断一个数是否为素数。
2. 对输入的正整数进行因数分解，从小到大枚举因子 k，如果 k 是素数且 num / k 也是素数，则输出 k 和 num / k。
3. 如果找不到符合条件的因子，则输出 -1, -1。

Java

import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    // 判断 n 是否为素数
    static boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(n) + 1; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int num = scanner.nextInt();

        int r1 = -1, r2 = -1;
        for (int k = 2; k < Math.sqrt(num) + 1; k++) {
            // 枚举因子 k, 如果 k 为素数且 num / k 为素数，则记录结果 k 和 num / k 并退出。
            if (num % k =