g5-04255. GESP-5级-2024-09-单选-第07题 未做

下面函数可以将 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;
}

• A. $O(n^2)$
• B. $O(n\log n)$
• C. $O(\sqrt{n}\log n)$
• D. $O(n)$