返回目录

题目描述

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

输入描述

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

输出描述

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

示例：

Python算法源码

def main():
    # 获取输入的整数
    n = int(input())
    # 调用函数并输出结果
    print(get_result(n))

def get_result(n):
    # 如果n为素数，则返回"-1 -1"
    if is_prime(n):
        return "-1 -1"

    # 遍历2到n之间的数，寻找n的因子
    for i in range(2, n):
        if n % i == 0:
            j = n // i
            # 如果i和j都是素数，则返回它们
            if is_prime(i) and is_prime(j):
                return f"{i} {j}" if i < j else f"{j} {i}"
            else:
                # 如果i或j不是素数，则直接结束循环
                break

    # 如果没有找到符合条件的素数对，则返回"-1 -1"
    return "-1 -1"

def is_prime(n):
    # 判断一个数是否为素数
    if n <= 3:
        return n > 1

    if n % 6 != 1 and n % 6 != 5:
        return False

    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6

    return True

if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>
#include <math.h>

// 素数判定函数
int isPrime(int n) {
    if (n <= 3) {
        return n > 1;
    }

    if (n % 6 != 1 && n % 6 != 5) {
        return 0;
    }

    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return 0;
        }
    }

    return 1;
}

// 算法入口函数
void getResult(int n) {
    // 如果n为素数，则必然不可能是两个素数之积
    if (isPrime(n)) {
        printf("-1 -1\n");
        return;
    }

    // 假设i为n的因子
    for (int i = 2; i < n; i++) {
        // 若n不能整除i,则i不是n的因子，继续下次循环，找新的i
        // 若n可以整除i,则i就是n的因子
        if (n % i == 0) {
            // j为n的另一因子
            int j = n / i;

            // 只有i,j因子都为素数时，n才是符合题意的素数之积
            if (isPrime(i) && isPrime(j)) {
                // 如果n为两个素数之积，则n只能分解为这两个因子，因为素数无法再次分解出其他因子，也就是说n不再有其他因子了（因子不包含1和自身）
                printf("%d %d\n", (i < j) ? i : j, (i < j) ? j : i);
                return;
            } else {
                // 如果i，j有一个不是素数因子，则说明n存在非素数因子，此时n不可能是素数之积
                // 如果i，j为相同的素数因子，则n不是满足题意的素数之积
                // 此时可以判定n不符合要求了，直接退出循环
                break;
            }
        }
    }

    printf("-1 -1\n");
}

int main() {
    int n;
    // 输入获取
    scanf("%d", &n);
    // 算法调用
    getResult(n);
    return 0;
}

Java算法源码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        getResult(n);
    }

    // 素数判定函数
    public static boolean isPrime(int n) {
        if (n <= 3) {
            return n > 1;
        }

        if (n % 6 != 1 && n % 6 != 5) {
            return false;
        }

        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }

        return true;
    }

    // 算法入口函数
    public static void getResult(int n) {
        // 如果n为素数，则必然不可能是两个素数之积
        if (isPrime(n)) {
            System.out.println("-1 -1");
            return;
        }

        // 假设i为n的因子
        for (int i = 2; i < n; i++) {
            // 若n不能整除i,则i不是n的因子，继续下次循环，找新的i
            // 若n可以整除i,则i就是n的因子
            if (n % i == 0) {
                // j为n的另一因子
                int j = n / i;

                // 只有i,j因子都为素数时，n才是符合题意的素数之积
                if (isPrime(i) && isPrime(j)) {
                    // 如果n为两个素数之积，则n只能分解为这两个因子，因为素数无法再次分解出其他因子，也就是说n不再有其他因子了（因子不包含1和自身）
                    System.out.println((i < j) ? i + " " + j : j + " " + i);
                    return;
                } else {
                    // 如果i，j有一个不是素数因子，则说明n存在非素数因子，此时n不可能是素数之积
                    // 如果i，j为相同的素数因子，则n不是满足题意的素数之积
                    // 此时可以判定n不符合要求了，直接退出循环
                    break;
                }
            }
        }

        System.out.println("-1 -1");
    }
}