What is the time complexity(in big O notation) given the following code and why?

64 Views Asked by At

The code provide below is number of divisors using prime factorization.

#include <vector>
using namespace std;

    vector<int> primes; // we'll preload primes once at the beginning
    int countDivisor(int n) {
      int divisor = 1;
      for (int i = 0; i < primes.size(); i++) {
        if (n % primes[i] == 0) {
          int cnt = 1;
          while (n % primes[i] == 0) {
            n /= primes[i];
            cnt++;
          }
          // add the number of times each prime divides n
          divisor += cnt;
        }
      }
      return divisor;
    }