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;
}
```