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

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

题目描述

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

输入描述

一个正整数num( 0 < n u m < 2 32 0 \lt num \lt 2^{32} 0<num<232)

输出描述

如果成功找到，以单个空格分割，从小到大输出两个素数，分解失败，请输出-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 == 0 && isPrime(k) && isPrime(num / k)) {
                r1 = k;
                r2 = num / k;
                break;
            }
        }

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

Python

import math


def is_prime(n) -> bool:
    """
    判断 n 是否为素数
    :param n:
    :return:
    """
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True


def solve(num: int):
    sq = int(math.sqrt(num) + 1)
    # 枚举因子 k, 如果 k 为素数且 num // k 为素数，则输出 k 和 num // k 。
    for k in range(2, sq + 1):
        if num % k == 0 and is_prime(k) and is_prime(num // k):
            print(k, num // k)
            return

    print(-1, -1)


if __name__ == "__main__":
    solve(int(input()))

C++

#include <bits/stdc++.h>
using namespace std;

// 判断 n 是否为素数
bool is_prime(int n)
{
    if (n < 2) {
        return false;
    }

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

int main()
{
    int num;
    cin >> num;

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

    cout << r1 << " " << r2 << endl;
    return 0;
}
    

‍❤️‍华为OD机试面试交流群（每日真题分享）： 加V时备注“华为od加群”