1. Divisors to sqrt
Try divisors only up to sqrt(n); a larger factor leaves a small cofactor.
for (let d = 2; d * d <= n; d += 1)Typorithm · medium
Prime Factorization
▷ Interactive algorithm labprime-factorizationmathtrial-divisiondivisorsremainder
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Prime Factorization
Math & Number Theory
Trial-divide by every candidate up to sqrt(n), pulling out each factor; any leftover is prime.
Trial division tests divisors from 2 upward, removing each factor completely before moving on.
Once a divisor d satisfies d*d > n, the remaining n (if above 1) must itself be prime.
Dividing n down as you go keeps the loop bound small and the work near sqrt(n).
Preparing algorithm lab…
01
Divide out every copy of d.
02
Loop only while d*d <= n.
03
Leftover n > 1 is prime.
function primeFactors(n) {
const factors = [];
for (let d = 2; d * d <= n; d += 1) {
while (n % d === 0) {
factors.push(d);
n = n / d;
}
}
if (n > 1) {
factors.push(n);
}
return factors;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Divide it out
Pull out every copy of the current divisor.
while (n % d === 0)3. Record factor
Each exact division records one prime factor.
factors.push(d)4. Shrink n
Dividing n keeps the search space small.
n = n / d5. Leftover prime
Any value above 1 left at the end is itself a prime factor.
if (n > 1)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.