Ep2-Prime-And-Sieve.md

Part 2 Episode 2/4: Prime Factorization and Prime Sieve

All the factors of a number n can be efficiently calculated in O(sqrt(N)) time.

Furthermore, one can find the prime factorization of a number as well in O(sqrt(N)) time.

Tutorial on Integer Factorization

---

A very efficient way to find all the prime factors less than or equal to a number N in O(N log(log(N))) is to use the Sieve of Eratosthenes.

Tutorial on Sieve of Eratosthenes

---

Another useful trick to know is that it is possible to factor a number in log(N) time if you are allowed to do O(N log(log(N))) pre processing.

Prime Factoring in log(N)

---

Here are some links to practice the aforementioned concepts:

1. Codeforces 26 A
2. SPOJ Fact 0
3. Codeforces 17 A

Challenge Problems

1. Codeforces 154 B
2. Codeforces 584 D
3. Codeforces 111 B