恒生电子嵌入式软件笔试编程题

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《嵌入式软件笔试-2023年真题汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

核心代码模式

第一题

给出一个正整数，请写一个算法来判断该数是质数还是合数，如果是合数，需输出该合数的质数因子。说明：直接使用开发语言提供的函数不得分。

判断：8 13 99 177 8888是质数还是合数

输入描述

8 13 99 177 8888

输出描述

质数或者合数

示例 1

输入：

100

输出：

[100]是合数.

100=2*2*5*5

说明：

整数100是合数，拆分后的质数因子为：2*2*5*5

#include <iostream>
#include <vector>
using namespace std;

// 函数用于判断数字是否是质数，并返回它的质数因子（如果有的话）
pair<bool, vector<int>> isPrimeAndFactors(int n) {
    if (n <= 1) return {false, {}};
    vector<int> factors;
    for (int i = 2; i*i <= n; i++) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 1) factors.push_back(n); // 如果n不是1，那么n是最后的质数因子
    return {factors.size() == 1 && factors[0] == n, factors};
}

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

    auto [isPrime, factors] = isPrimeAndFactors(n);
    if (isPrime) {
        cout << n << " 是质数." << endl;
    } else {