华为OD统一考试 -素数之积

题目描述

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

输入描述

一个正整数 num 0 < num < 2147483647

输出描述

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

用例

题目解析

首先，要了解素数概念，及素数判定方法

素数又叫质数，指的是“大于1的整数中，只能被1和这个数本身整除的数”。素数也可以被等价表述成：“在正整数范围内，大于1并且只有1和自身两个约数的数”。

中学数学常见的素数是20以内的素数：2、3、5、7、11、13、17、19。

素数的相关知识小结：

1、最小的素数是2，最小的合数是4。【注】最小的素数和最小的合数都是偶数。

2、大于2的素数都是奇数，2是素数中唯一的偶数。

3、1既不是素数也不是合数。

4、大于1的正整数中，不是素数就是合数

5、素数不全是奇数，也可以是偶数，如：2。

其次再来解析题目

给定一个 32 位正整数，请对其进行因数分解，找出是哪两个素数的乘积。

15 可以被分解为 3 5，由于是这两个素数乘积为15，所以判定为分解成功；

27 可以被分解为 3 3 3，由于不是两个素数的乘积，所以判定为分解失败；

这里，我理解题目想表达的意思是，

给定的正整数，要支持

只能

分解为

两个素数因子

，且两个素数乘积要为给定的正整数，那么

• 若给定的正整数为素数，则只能分解为1和自身，而1不是素数，所以判定为分解失败

这可以帮助我们缩小了给定的正