【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【数学】2023C-素数之积【欧弟算法】全网注释最详细分类最全的华为OD真题题解

发布时间:2024年01月05日

题目描述与示例

题目描述

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

输入描述

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

输出描述

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

示例

输入

15

输出

3 5

说明

因数分解后,找到两个素数35,使得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为答案。

上述过程慢的原因主要在于,计算ab是否是素数的环节。

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

质数筛

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

  1. 构建长度为num+1的质数筛数组sievesieve[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

# 题目:【模拟】2023C-素数之积
# 分值:100
# 作者:许老师-闭着眼睛学数理化
# 算法:数学
# 代码看不懂的地方,请直接在群上提问


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 <vector>
#include <cmath>
#include <unordered_set>

std::vector<int> sieve_of_eratosthenes(int n) {
    std::vector<bool> sieve(n + 1, 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;
            }
        }
    }

    std::vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (sieve[i]) {
            primes.push_back(i);
        }
    }

    return primes;
}

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

    std::vector<int> primes = sieve_of_eratosthenes(num);
    std::unordered_set<int> primes_set(primes.begin(), primes.end());

    bool isFind = false;
    for (int a : primes) {
        if (num % a == 0) {
            int b = num / a;
            if (primes_set.find(b) != primes_set.end()) {
                std::cout << a << " " << b << std::endl;
                isFind = true;
                break;
            }
        }
    }

    if (!isFind) {
        std::cout << -1 << " " << -1 << std::endl;
    }

    return 0;
}

时空复杂度

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

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


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

文章来源:https://blog.csdn.net/weixin_48157259/article/details/135406361
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。