Prime Factorization & Divisors
Break N into prime powers and count divisors.
Prime Factorization & Divisors is a free Coding Interview Prep lesson on CoddyKit. This is 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, and your progress syncs across the web and the CoddyKit app. The Coding Interview Prep course includes 4 lessons in total.
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. ✅
Learn Coding Interview Prep with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 90
- Lessons
- 360
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. 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. The Coding Interview Prep course includes 4 lessons in total.
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, so you can start here or from the beginning and move at your own pace. This is lesson 4 of 4.
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