下面函数可以将 n 的所有质因数找出来，其时间复杂度是（ ）。

#include <iostream>
#include <vector>

vector<int> get_prime_factors(int n) {
    vector<int> factors;

    while (n % 2 == 0) {
        factors.push_back(2);
        n /= 2;
    }

    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }

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

    return factors;
}

{{ select(1) }}

• $O(n^2)$
• $O(n \log n)$
• $O(\sqrt{n} \log n)$
• $O(n)$