GESP 五级 · GESP 202412 C++ 五级 第 6 题

唯一分解定理表明，每个大于 $1$ 的自然数可以唯一地写成若干个质数的乘积。下面函数将自然数 $n$ 的所有质因素找出来，横线上能填写的最佳代码是（ ）。

#include <vector>
vector<int> get_prime_factors(int n) {
    vector<int> factors;
    if (n <= 1) {
        cout << "输入的数必须是大于1的正整数" << endl;
        return;
    }
    while (n % 2 == 0) {
        factors.push_back(2);
        n /= 2;
    }

    // 在此处填入代码
    while (n % i == 0) {
        factors.push_back(i);
        n /= i;
    }

    if (n > 2) {
        factors.push_back(n);
    }
    return factors;
}

质数判定优化：只需检查2到√n。偶数除了2都不是质数。判断素数的时间复杂度O(√n)。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

【考点】试除法质因数分解｜循环优化（i*i≤n）｜奇偶步长优化

1. 🎯 考纲定位

GESP 五级 C++ 考纲"算法与数据结构"模块，重点考察试除法求质因数和循环边界优化。命题人卡住的是考生对循环条件和步长的理解——这是五级和四级最大的分水岭。