题目来自于博主算法大师的专栏：最新华为OD机试C卷+AB卷+OJ（C++JavaJSPy） https://blog.csdn.net/banxia_frontend/category_12225173.html

题目描述

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

输入描述

一个正整数num，0 < num <= 2147483647

输出描述

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

用例

输入

15

输出

3 5

输入

27

输出

-1 -1

代码

#include <stdio.h>
#include <stdlib.h>

// 定义一个判断整数是否为素数的函数
int isPrime(int n) {
    // 对于小于等于3的数，只有2和3是素数
    if (n <= 3) {
        return n > 1;
    }
    // 遍历从2到sqrt(n)，检查是否有能被n整除的数
    for (int i = 2; i * i <= n; i++) {
        // 如果找到一个能整除n的数i，则该数不是素数
        if (n % i == 0) {
            return 0;
        }
    }
    // 若遍历结束后未找到能整除n的数，则n是素数
    return 1;
}

int main() {
    int num;           // 定义变量num存储用户输入的32位正整数
    scanf("%d", &num); // 读取用户输入的整数

    // 判断num本身是否为素数，如果是素数则无法进行因数分解
    if (isPrime(num)) {
        printf("-1 -1\n"); // 输出分解失败标识
        return 0;          // 结束程序
    }

    // 遍历可能的因子，寻找合适的两个素数因子
    for (int i = 2; i * i <= num; i++) {
        // 如果当前数i能整除num
        if (num % i == 0) {
            int j = num / i; // 计算另一个因子j
            // 检查i和j是否都是素数
            if (isPrime(i) && isPrime(j)) {
                // 如果两者均为素数，则输出分解结果（按升序排列）
                printf("%d %d\n", i < j ? i : j, j > i ? j : i);
                return 0; // 结束程序
            }
        }
    }

    // 如果循环结束仍未找到合适的素数因子，则输出分解失败标识
    printf("-1 -1\n");
    return 0; // 结束程序
}