Prime Factorization

The this post, we introduced how to get all prime numbers from 1 to n in o(nloglogn) time. Base on which, we can do prime factorization in O(logn) time.

constexpr int kMaxNum = 100001;
// Finds all prime numbers in [2, kMaxNum];
// Finds the smallest prime factor for any number
int num_to_smallest_prime_factor[kMaxNum + 1]
// O(nloglogn)
void FindParimes() {
    bool is_prime[kMaxNum + 1];
    memset(is_prime, 1, sizeof(is_prime));
    memset(num_to_smallest_prime_factor, 0, sizeof(num_to_smallest_prime_factor));
    for (int i = 2; i <= kMaxNum; ++i) {
        if (!is_prime[i]) {
            continue;
        }
        num_to_smallest_prime_factor[i] = i;
        for (long long j = (long long)i * i; j <= kMaxNum; j += i) {
            if (num_to_smallest_prime_factor[j] == 0) {
                num_to_smallest_prime_factor[j] = i;
            }
            is_prime[j] = false;
        }
    }
}

// Returns all prime factors of num
// O(logn) since num is divided by at least 2 each time 
vector<int> PrimeFactorization(int num) {
    vector<int> res;
    while (num > 1) {
        int prime = num_to_smallest_prime_factor[num];
        res.push_back(prime);
        while (num % prime == 0) {
            num /= prime;
        }
    }
    return res;
}