Prime Factorization & Divisors
Break N into prime powers and count divisors.
Prime Factorization & Divisors is a free Coding Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Break N Apart
Every integer above 1 is a unique product of primes. Finding that breakdown, its prime factorization, unlocks many number-theory problems. 🧩
The Trial Division Idea
Pull out the smallest prime that divides n, divide it away, and repeat. This simple trial division peels n down to 1.
Loop to the Root
Test divisors i while i*i stays at or below n. Beyond the square root, at most one prime factor can remain.
while i * i <= n:
...Extract Each Factor
While i divides n, keep dividing and record i. This captures the full power of that prime before moving on.
while n % i == 0:
factors.append(i)
n //= iThe Leftover Prime
After the loop, if n is still above 1 it is itself a prime factor larger than the square root. Add it once.
if n > 1:
factors.append(n)The Full Routine
Together this gives factorization in O(sqrt n) time, returning every prime with its full multiplicity in order.
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return fGroup into Powers
For divisor counting you want each prime with its exponent, like 2^3 not 2,2,2. A Counter tallies the repeats cleanly.
from collections import Counter
exp = Counter(factorize(n))The Divisor Formula
If n is p1^a times p2^b, the number of divisors is (a+1) times (b+1). Each exponent gets one extra choice.
Count the Divisors
Multiply one plus each exponent across all primes. This gives the total divisor count without listing them out.
count = 1
for e in exp.values():
count *= (e + 1)Sum of Divisors
A related formula sums divisors using each prime's geometric series. Knowing it helps with perfect number and aliquot problems.
Speed with a Sieve
For many factorizations, precompute each number's smallest prime factor with a sieve. Then each query factorizes in log n steps.
Quick Check
Apply the divisor-counting formula to a concrete number.
Recap
You can now factorize N by trial division in O(sqrt n), capture the leftover prime, group exponents, and count divisors with the product formula. ✅
Frequently asked questions
Is the “Prime Factorization & Divisors” lesson free?
Yes — the full text of “Prime Factorization & Divisors” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Prime Factorization & Divisors”?
Break N into prime powers and count divisors. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Prime Factorization & Divisors” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- GCD, LCM & the Euclidean Algorithm
- Primality Testing up to sqrt(n)
- Sieve of Eratosthenes
- Prime Factorization & Divisors