Trial division factorization complexity

Revision en2, by vaibhavmisra, 2023-01-08 14:46:56

Hey folks, how the below code from here has O(√N) time complexity? Shouldn't it be equal to the number of prime factors of n?

vector<long long> trial_division1(long long n) {
    vector<long long> factorization;
    for (long long d = 2; d * d <= n; d++) {
        while (n % d == 0) {
            factorization.push_back(d);
            n /= d;
        }
    }
    if (n > 1)
        factorization.push_back(n);
    return factorization;
}
Tags prime-factorisation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English vaibhavmisra 2023-01-08 14:47:34 2 Tiny change: 'n) has O(√N) time com' -> 'n) has O(√n) time com'
en2 English vaibhavmisra 2023-01-08 14:46:56 72
en1 English vaibhavmisra 2023-01-08 14:41:16 582 Initial revision (published)