素数之积 - 华为OD机试题

题目描述

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

输入描述

一个正整数num(0<num<2^32)

输出描述

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

示例一

代码语言：javascript复制

输入：
15

输出：
3 5

示例二

代码语言：javascript复制

输入：
27

输出：
-1 -1

java题解

题解

代码语言：javascript复制

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

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

代码语言：javascript复制

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 == 0 && isPrime(k) && isPrime(num / k)) {
                r1 = k;
                r2 = num / k;
                break;
            }
        }

        System.out.println(r1   " "   r2);
    }
}

网络安全 int 函数 华为 数据

0 人点赞