题目描述与示例

题目描述

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

题目练习网址：https://www.algomooc.com/problem/P2528

输入描述

1`个正整数`num
0 < num <= 2147483647

输出描述

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

示例

输入

15

输出

3 5

说明

因数分解后，找到两个素数3和5，使得3*5=15，按从小到大排列后，输出3 5

解题思路

经典的大数分解问题。

关于素数相关的内容，可以详看算法题中常用数学概念、公式、方法汇总 里的相关部分。

暴力解

比较容易想到的暴力解法包含以下步骤

1. 从小到大枚举所有小于sqrt(num)的数a
2. 判断num是否可以整除a，若
   1. 不可以，则直接跳过。遍历下一个a
   2. 可以，则进行后续判断
3. 判断a是否是素数，若
   1. 不是，则直接跳过。遍历下一个a
   2. 是，则进行后续判断
4. 判断b = num // a是否是素数，若
   1. 不是，则直接跳过。遍历下一个a
   2. 是，则a b为答案。

上述过程慢的原因主要在于，计算a或b是否是素数的环节。

可以使用质数筛来优化上述过程。

质数筛

使用质数筛解决上述大数分解的过程如下

1. 构建长度为num+1的质数筛数组sieve。sieve[i]是True表示i是质数，sieve[i]是False表示i是合数。
2. 枚举质数筛中每一个质数a，即sieve[a] = True的下标。
3. 判断num是否可以整除a，若
   1. 不可以，则直接跳过。遍历下一个a
   2. 可以，则进行后续判断
4. 判断b = num // a是否是素数，若
   1. 不是，则直接跳过。遍历下一个a
   2. 是，则a b为答案。

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频


from math import floor, sqrt


# 使用埃氏筛计算数组
def sieve_of_eratosthenes(n):
    # 构建埃氏筛，长度为n+1，初始化均为True，表示默认为质数
    sieve = [True] * (n + 1)
    # 0和1不是质数
    sieve[0], sieve[1] = False, False
    # 枚举从2到floor(sqrt(x))的每一个数x
    for x in range(2, floor(sqrt(n)) + 1):
        # 如果x是一个质数，则说明其m倍（m >= 2）的所有正整数是合数
        if sieve[x] == True:
            # 将mx标记为False
            for i in range(2 * x, n + 1, x):
                sieve[i] = False

    # 退出循环后，sieve中所有为True的元素下标为质数
    primes = [i for i in range(n + 1) if sieve[i]]
    return primes


num = int(input())
# 计算所有小于num的素数
primes = sieve_of_eratosthenes(num)
primes_set = set(primes)

# 初始化一个标记，表示是否找到一组素数
isFind = False
# 遍历所有小于num的素数a
for a in primes:
    # 如果num可以整除a
    if num % a == 0:
        # 则计算b是否也是素数
        b = num // a
        # 如果是，则输出(a, b)
        # 同时标记isFind为True，表示计算得到一组答案
        # 同时退出循环
        if b in primes_set:
            print(a, b)
            isFind = True
            break

# 如果退出循环后，isFind仍为False，则输出(-1, -1)
if isFind == False:
    print(-1, -1)

Java

import java.util.*;

public class Main {
    public static List<Integer> sieveOfEratosthenes(int n) {
        boolean[] sieve = new boolean[n + 1];
        Arrays.fill(sieve, true);
        sieve[0] = sieve[1] = false;

        for (int x = 2; x * x <= n; ++x) {
            if (sieve[x]) {
                for (int i = x * x; i <= n; i += x) {
                    sieve[i] = false;
                }
            }
        }

        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; ++i) {
            if (sieve[i]) {
                primes.add(i);
            }
        }

        return primes;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();

        List<Integer> primes = sieveOfEratosthenes(num);
        Set<Integer> primesSet = new HashSet<>(primes);

        boolean isFind = false;
        for (int a : primes) {
            if (num % a == 0) {
                int b = num / a;
                if (primesSet.contains(b)) {
                    System.out.println(a + " " + b);
                    isFind = true;
                    break;
                }
            }
        }

        if (!isFind) {
            System.out.println("-1 -1");
        }
    }
}

C++

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

// 使用埃氏筛计算素数
void sieve_of_eratosthenes(int n, vector<bool> &sieve) {
    // 初始化为全为 true，表示默认所有数为质数
    for (int i = 0; i <= n; i++) {
        sieve[i] = true;
    }
    sieve[0] = sieve[1] = false; // 0 和 1 不是质数

    // 枚举从 2 到 sqrt(n) 的每一个数 x
    for (int x = 2; x <= static_cast<int>(sqrt(n)); x++) {
        if (sieve[x]) { // 如果 x 是质数
            for (int i = 2 * x; i <= n; i += x) {
                sieve[i] = false; // 标记 x 的倍数为合数
            }
        }
    }
}

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

    // 创建埃氏筛数组
    vector<bool> sieve(num + 1, true);
    sieve_of_eratosthenes(num, sieve);

    bool isFind = false; // 标记是否找到答案

    // 遍历所有小于 num 的素数
    for (int a = 2; a <= num; a++) {
        if (sieve[a] && num % a == 0) { // 如果 a 是素数且 num 可以整除 a
            int b = num / a; // 计算 b
            if (b <= num && sieve[b]) { // 如果 b 也是素数
                cout << a << " " << b << endl;
                isFind = true;
                break;
            }
        }
    }

    // 如果未找到答案
    if (!isFind) {
        cout << "-1 -1" << endl;
    }

    return 0;
}

C

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

// 使用埃氏筛计算素数
void sieve_of_eratosthenes(int n, bool *sieve) {
    // 初始化为全为 true，表示默认所有数为质数
    for (int i = 0; i <= n; i++) {
        sieve[i] = true;
    }
    sieve[0] = sieve[1] = false; // 0 和 1 不是质数

    // 枚举从 2 到 sqrt(n) 的每一个数 x
    for (int x = 2; x <= (int)sqrt(n); x++) {
        if (sieve[x]) { // 如果 x 是质数
            for (int i = 2 * x; i <= n; i += x) {
                sieve[i] = false; // 标记 x 的倍数为合数
            }
        }
    }
}

int main() {
    int num;
    scanf("%d", &num);

    // 创建埃氏筛数组
    bool *sieve = (bool *)malloc((num + 1) * sizeof(bool));
    sieve_of_eratosthenes(num, sieve);

    int isFind = 0; // 标记是否找到答案

    // 遍历所有小于 num 的素数
    for (int a = 2; a <= num; a++) {
        if (sieve[a] && num % a == 0) { // 如果 a 是素数且 num 可以整除 a
            int b = num / a; // 计算 b
            if (b <= num && sieve[b]) { // 如果 b 也是素数
                printf("%d %d\n", a, b);
                isFind = 1;
                break;
            }
        }
    }

    // 如果未找到答案
    if (!isFind) {
        printf("-1 -1\n");
    }

    free(sieve); // 释放内存
    return 0;
}

Node JavaScript

// 使用埃氏筛计算素数
function sieveOfEratosthenes(n) {
    const sieve = Array(n + 1).fill(true);
    sieve[0] = sieve[1] = false; // 0 和 1 不是质数

    for (let x = 2; x <= Math.floor(Math.sqrt(n)); x++) {
        if (sieve[x]) { // 如果 x 是质数
            for (let i = 2 * x; i <= n; i += x) {
                sieve[i] = false; // 标记 x 的倍数为合数
            }
        }
    }

    return sieve;
}

// 主函数
function main() {
    const readline = require('readline');
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout,
    });

    rl.question('', (num) => {
        num = parseInt(num);

        const sieve = sieveOfEratosthenes(num);

        let isFind = false;

        // 遍历所有小于 num 的素数
        for (let a = 2; a <= num; a++) {
            if (sieve[a] && num % a === 0) { // 如果 a 是素数且 num 可以整除 a
                const b = num / a;
                if (b <= num && sieve[b]) { // 如果 b 也是素数
                    console.log(`${a} ${b}`);
                    isFind = true;
                    break;
                }
            }
        }

        // 如果未找到答案
        if (!isFind) {
            console.log("-1 -1");
        }

        rl.close();
    });
}

main();

Go

package main

import (
    "bufio"
    "fmt"
    "math"
    "os"
    "strconv"
    "strings"
)

// 使用埃氏筛计算素数
func sieveOfEratosthenes(n int) []bool {
    sieve := make([]bool, n+1)
    for i := 2; i <= n; i++ {
        sieve[i] = true
    }

    for x := 2; x <= int(math.Sqrt(float64(n))); x++ {
        if sieve[x] { // 如果 x 是质数
            for i := 2 * x; i <= n; i += x {
                sieve[i] = false // 标记 x 的倍数为合数
            }
        }
    }
    return sieve
}

func main() {
    // 读取输入
    reader := bufio.NewReader(os.Stdin)
    input, _ := reader.ReadString('\n')
    input = strings.TrimSpace(input)
    num, _ := strconv.Atoi(input)

    sieve := sieveOfEratosthenes(num)

    isFind := false // 标记是否找到答案

    // 遍历所有小于 num 的素数
    for a := 2; a <= num; a++ {
        if sieve[a] && num%a == 0 { // 如果 a 是素数且 num 可以整除 a
            b := num / a
            if b <= num && sieve[b] { // 如果 b 也是素数
                fmt.Printf("%d %d\n", a, b)
                isFind = true
                break
            }
        }
    }

    // 如果未找到答案
    if !isFind {
        fmt.Println("-1 -1")
    }
}

时空复杂度

时间复杂度：O(Nlog(NlogN))。构建质数筛所需要的时间

空间复杂度：O(1)。除了输入的序列，仅需若干常数变量维护遍历过程。