题解 | #质数因子# 时间复杂度太复杂的数学加持下解法

又是一个坑爹题, 在现代CPU上进行一次操作可能需要1 ~ 5时钟周期, 如果一个cpu主频为3Ghz的话, 一个时钟周期 = 1 / 3GHZ = 1 / 3*10^9HZ ≈ 0.33 * 10^-9 秒, 也就是说我们稍微搞一搞可能就超时了, 特别是在用到复杂的数据结构或者其他操作的时候, 所以我们必须借助数论中的结论来达到100%的通过率. 题目中的解法 是我从gpt-4那学到的, 注释就不写了,先写下思路, 最后放一下gpt-4的回答.

如果没做出来题目的话先给思路

1. 弄一个计数器i来遍历所有的数, 每次循环i+1
2. 如果n可以被i整除, 那么把i压入双向列表, 让n=n/i, 然后让i=0重新开始寻找下一个可以分解的质数
3. 当i=n的时候结束, 此时如果i不等于1的话, 将i压入双向列表
4. 利用标准库里的algorithm库中的sort函数进行排序
5. 打印输出

----------------------------------------------

其中假设大家都做出来了题目, 只是时间复杂度达不到要求.

1. 我们设输入的大数为n
2. 任何一个整数都可以表示为a*b, 必然有一个因子小于或等于 根号n, 一个大于等于根号n, 如果两个都大于根号(n)或者小于根号(n)均无法构造整数n, 这是由简单的不等式性质得到的结论.
3. 利用上述性质我们可以知道, 如果在原有的程序上迭代到根号(n)以后, 经过不断的自除操作后最终n'仍然大于1, 那么我们可以认为n'也是一个质数因子, 原因是: 它已经被比根号(n)小的数除完了, 那么它就只能被 1 和它本身整除. 如果它还能继续被比根号(n)大的数整除, 那得到的数一定是1, 换句话说也就是他自身, 利用2的性质可以知道, 如果是2-根号(n)之间的数的话, 之前就已经被分解过了, 没被分解过说明你的代码不够健全, 退出循环的时候把可能性漏掉了. 所以最后得出来的大于1的n'不可能得到一个合数. 蓝色字部分一定要想明白, 想不明白的话动笔画一画, 如果还是不明白的话死记硬背记住这个结论就行.

-----------------------------------------------

gpt-4的回答:

这个方法的数学原理是基于质数分解的性质。质数分解定理（也称为唯一分解定理）是数论中的一个重要定理，它指出任何一个大于1的自然数都可以唯一地表示为若干个质数的乘积。

在这个方法中，我们遍历所有小于等于 sqrt(n) 的数，这是因为如果一个数 n 有因子 a 和 b，那么必然有一个因子小于或等于 sqrt(n)。为了证明这一点，可以假设两个因子都大于 sqrt(n)，那么它们的乘积 a * b 会大于 n，这与它们是 n 的因子相矛盾。所以，在寻找质数因子时，我们只需要检查小于等于 sqrt(n) 的数。

在循环中，我们检查 n 是否可以被当前的数 i 整除。如果可以整除，说明 i 是一个质数因子。然后我们将 n 除以 i，并继续检查 n 是否仍然可以被 i 整除。这样，我们可以找到 n 的所有质数因子，并将它们添加到结果列表中。

在循环结束后，如果 n 大于1，那么 n 本身是一个质数因子（或者是剩下的质数因子的乘积）。我们将其添加到结果列表中。

这个方法相较于暴力方法（遍历所有小于 n 的数）具有更低的时间复杂度，因为它只需要遍历小于等于 sqrt(n) 的数，并在找到质数因子后，将 n 除以这些因子，从而减少了后续循环的迭代次数。

---------------------------------------

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

void prime_factors(int n, deque<int>& factors);
void print_factors(const deque<int>& factors);

int main() {
    int inputInt;
    cin >> inputInt;
    deque<int> factors;
    prime_factors(inputInt, factors);
    sort(factors.begin(), factors.end());
    print_factors(factors);
}

void prime_factors(int n, deque<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);
    }
}

void print_factors(const deque<int>& factors) {
    for (deque<int>::const_iterator it = factors.begin(); it != factors.end(); ++it) {
        cout << *it << ' ';
    }
}