【华为OD机试真题 C++】素数之积 【2022 Q4 | 100分】

前言

■ 题目描述

【素数之积】

RSA加密算法在网络安全世界中无处不在，它利用了极大整数因数分解的困难度，数据越大，安全系数越高。

给定一个32位正整数，请对其进行因数分解，找出是哪两个素数的乘积。

输入描述

一个正整数num

0 < num <= 2147483647

输出描述

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

示例1 输入输出示例仅供调试，后台判题数据一般不包含示例

输入

15

输出

3 5

说明

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

示例2 输入输出示例仅供调试，后台判题数据一般不包含示例

输入

27

输出

-1 -1

说明

通过因数分解，找不到任何素数，使得他们的乘积为27，输出-1 -1。

C++代码实现：

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

using namespace std;

bool isPrime_3( int num )
{
    if(num == 2|| num== 3 )
        return true;
    if(num % 6 != 1 && num % 6 != 5)
        return false;
    int tmp = sqrt(num);
    for(int i = 5;i <= tmp; i += 6 )
        if(num % i == 0|| num % (i+2) == 0 )
            return false;
    
    return true ;
}

void Prime(int n, vector<int>& vec)
{
    if (n <= 1)
    {
        return;
    }
    for (int i = 2; i < n; ++i)
    {
        if (isPrime_3(i))
        {
            vec.push_back(i);
        }
    }
    return;
}

void IsDecode(int n, vector<int> prime_vec, vector<int>& decode_prime_vec)
{
    for (int & i : prime_vec)
    {
        if (n % i == 0)
        {
            decode_prime_vec.push_back(i);
            n /= i;
        }
    }
}

int main(int argc, char** argv)
{
    vector<int> prime_vec;
    vector<int> decode_prime_vec;
    int n;
    cin >> n;
    Prime(n, prime_vec);
    IsDecode(n, prime_vec, decode_prime_vec);
    if (decode_prime_vec.empty())
    {
        cout << -1 << "," << -1 << endl;
        return 0;
    }
    for (int i = 0; i < decode_prime_vec.size(); i++)
    {
        cout << decode_prime_vec[i];
        if (i != decode_prime_vec.size()-1)
        {
            cout << ",";
        }
    }
    return 0;
}