下面函数可以将 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²)
- B. O(n log n)
- C. O(√n log n)
- D. O(n)
正确答案：C