E卷-刷题笔记合集🔗

素数之积-RSA加密算法

问题描述

LYA是一名网络安全工程师,她经常需要处理一些加密数据。最近她遇到了一个有趣的问题:给定一个 位正整数,判断它是否可以表示为两个素数的乘积。如果可以,请输出这两个素数,按从小到大的顺序输出。

输入格式

一个正整数 。

输出格式

如果 可以表示为两个素数的乘积,以单个空格分割,从小到大输出这两个素数。如果无法分解,输出 。

样例输入

15

样例输出

3 5

样例解释

可以表示为 ,其中 和 都是素数。

样例输入

27

样例输出

-1 -1

样例解释

无法表示为两个素数的乘积。

数据范围

题解

枚举

我们可以使用一种简单的方法来寻找给定整数的素数因子。首先,我们从2开始,检查num是否能被2整除。如果能够整除,我们将2作为一个因子,并将num除以2。重复这个过程,直到num不能被2整除为止。然后,我们尝试3,5,7,...,直到找到两个素数因子或者num变为1。如果找到两个素数因子,我们输出它们。否则,我们输出-1 -1。

参考代码

• Python

def find_prime_factors(num):
    """
    寻找给定数字的素数因子
    :param num: 输入的正整数
    :return: 素数因子列表
    """
    factors = []
    i = 2
    while num > 1:
        if num % i == 0:
            factors.append(i)
            num //= i
        else:
            i += 1
        # 如果因子数量超过2，直接退出循环
        if len(factors) > 2:
            break
    return factors

# 读取输入
num = int(input())

# 寻找素数因子
factors = find_prime_factors(num)

# 输出结果
if len(factors) == 2:
    print(factors[0], factors[1])
else:
    print(-1, -1)

• C

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

#define MAX_FACTORS 2

// 寻找给定数字的素数因子
int find_prime_factors(unsigned int num, int* factors) {
    int count = 0;
    int i = 2;
    
    while (num > 1 && count < MAX_FACTORS) {
        if (num % i == 0) {
            factors[count++] = i;
            num /= i;
        } else {
            i++;
        }
    }
    
    return count;
}

int main() {
    unsigned int num;
    int factors[MAX_FACTORS];
    
    // 读取输入
    scanf("%u", &num);
    
    // 寻找素数因子
    int count = find_prime_factors(num, factors);
    
    // 输出结果
    if (count == 2) {
        printf("%d %d\n", factors[0], factors[1]);
    } else {
        printf("-1 -1\n");
    }
    
    return 0;
}

• Javascript

function findPrimeFactors(num)