一、题目

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

二、输入

1
2
一个正整数num
0 < num <= 2147483647

三、输出

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

四、示例

1
2
3
4
5
输入：
15

输出：
3 5
  • 说明：
    • 因数分解后3 * 5 = 15
    • 从小到大后输出 3 5

五、题解

今天来一个轻松但是比较有技巧的算法。判断一个数是否为质数相信都会，但是如何高效的判断大量数是否为质数是有比较大的优化空间的。
本文中的埃氏筛法就是一个比较有技巧性的算法。基本思路先把所有的数都当作质数，然后从 2 开始，把倍数筛除掉，留下的 2、3、5、7 就是要求解的结果了。

5.1 Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package org.stone.study.algo.ex202411;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * RSA加密算法在网络安全世界中无处不在，
 * 它利用了极大整数因数分解的困难度，数据越大，安全系数越高，
 * 给定一个 32 位正整数，请对其进行因数分解，找出是哪两个素数的乘积。
 */
public class RsaAlgo {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int p = scanner.nextInt();
        int[] arr = RsaDecompose(p);
        System.out.println(arr[0] + " " + arr[1]);
    }

    /**
     * 分解 RSA 质数：埃氏筛法
     * @param p
     * @return
     */
    private static int[] RsaDecompose(int p) {
        int[] arr = new int[2];
        Set<Integer> factors = new HashSet<>();
        int temp = p;
        int n = 2;
        while ( temp != 1) {
            if (temp % n == 0) { // 2和 2 的倍数，3和 3 的倍数，5和 5 的倍数，也就是埃氏筛法
                factors.add(n);
                temp /= n;
            } else {
                ++n;
            }
        }

        for (Integer factor1 : factors) {
            for (Integer factor2 : factors) {
                if (factor1 * factor2 == p) {
                    arr[0] = Math.min(factor1, factor2);
                    arr[1] = Math.max(factor1, factor2);
                    return arr;
                }
            }
        }
        return new int[]{-1, -1};
    }
}

5.2 Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def rsaDecompose(p):
    """
    分解p为两个素数的乘积
    :param p:
    :return:
    """
    factors = set()
    temp = p
    n = 2
    # 求小于 p 的所有素数：埃氏筛法
    while temp > 1:
        if temp % n == 0:
            factors.add(n)
            temp = temp // n
        else:
            n += 1
    if len(factors) != 2:
        return [-1, 1]
    
    for m in factors:
        for n in factors:
            if m * n == p and m!= n:
                return [min(m, n), max(m, n)]
    return [-1, 1]


if __name__ == '__main__':
    p = int(input())
    arr = rsaDecompose(p)
    print(arr)