cf.completefrontend
MATH & GEOMETRY · CORE

Prime factorization

Break a number into the primes that multiply to it by dividing out each divisor from 2 up to the square root.

Time O(√n)Space O(log n)4 practice problemsStep-through picture

The idea

Every whole number above 1 can be written as a product of primes in exactly one way, apart from order. 360 = 2 × 2 × 2 × 3 × 3 × 5. That list is its prime factorization, and it tells you almost everything about the number's divisors.

Trial division finds it: try dividing by d = 2, 3, 4, 5, .... Each time d divides the number, record d and divide it out, and keep dividing by the same d while you can. Because the small factors are removed first, any d that divides what's left is always prime: its own smaller factors were already removed.

You only need to try d while d * d <= rest. If no such d divides rest and rest is still above 1, then rest itself is prime and is the last factor.

An everyday example

Breaking a chocolate bar into the smallest pieces

A chocolate bar has 360 squares. You break it into equal halves while you can: 180, 90, 45. Halves no longer work, so you try thirds: 15, then 5. Then fourths can't work anymore, since you already removed every half. Five squares can't be split into equal groups smaller than itself, so you stop. The breaks you made, 2, 2, 2, 3, 3, and the last piece, 5, are the prime factors.

How the example maps to the code
In the exampleIn the code
The part of the bar still to breakrest
Trying to split into d equal groupsrest % d === 0
Making the break and writing it downfactors.push(d); rest /= d
A piece that can't be split anymoreif (rest > 1) factors.push(rest)

From the slow way to prime factorization

  1. Start with the obvious way: list every number from 2 to n, check which ones divide n, and keep only the ones that are prime. For a number near a billion that means a billion divisions plus a primality test for each divisor found. Nearly all of that work is wasted on numbers that don't divide n at all.
  2. Look at the smallest divisor of n above 1. It must be prime: if it had a smaller factor, that factor would also divide n and would be smaller. So find the smallest divisor d, record it, and divide it out. What's left, rest = n / d, is a smaller number with the remaining factors, and the same idea applies to it.
  3. Don't restart from 2 after each division. Once every 2 has been divided out with a while loop, 2 can never divide rest again, and neither can 4, 6, or any multiple of 2. So d only ever moves forward, and each d that divides rest is automatically prime: its own prime factors were all removed earlier.
  4. Finally, stop early. If rest has no factor d with d * d <= rest, it can't be split into two factors, so it is 1 or a prime. Because rest shrinks as factors come out, this bound shrinks too. Loop d while d * d <= rest, divide out each d fully, and push whatever rest is left above 1. That loop is trial division.

How it works

  1. Start with an empty factors list and rest = n.
  2. Try each d from 2 while d * d <= rest.
  3. While d divides rest, push d to factors and divide rest by d.
  4. Move on to the next d.
  5. After the loop, if rest > 1, it is prime: push it as the last factor.
  6. Return factors, which is in ascending order.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function primeFactors(n) {
  2. const factors = [];
  3. let rest = n;
  4. for (let d = 2; d * d <= rest; d++) {
  5. while (rest % d === 0) {
  6. factors.push(d);
  7. rest /= d;
  8. }
  9. }
  10. if (rest > 1) factors.push(rest);
  11. return factors;
  12. }

How fast it is

TimeO(√n)
Extra memoryO(log n)

The loop tries divisors up to the square root of n. A number has at most log₂ n prime factors, so the list is short.

  • Best caseO(log n)

    A power of a small prime, like 2^20. The while loop at d = 2 divides 20 times, rest becomes 1, and the outer loop ends after a single d.

  • Average caseO(√n)

    The bound is √n, but most numbers lose small factors quickly. For random numbers below a billion the loop tried about 3,600 values of d on average, against a bound of about 31,600.

  • Worst caseO(√n)

    A prime, like 999999937, needs 31,621 tries. A product of two primes close to each other, like 999979 × 999983, needs 999,978 tries before rest changes.

Common mistakes

  • Using if instead of while for dividing. Repeated primes like the three 2s in 360 are only recorded once.
  • Forgetting the last step if (rest > 1). A large prime factor, like 13 in 26, is lost.
  • Looping d up to n instead of √rest. For a prime near a billion that's a billion steps instead of about 31,623.
  • Factorizing many numbers one by one when they're all small. A sieve that stores each number's smallest prime factor is faster.

When to use it

Look for these clues in a problem:

  • The problem asks for the prime factors, the number of divisors, or the sum of divisors.
  • You need to know which primes divide a number, or simplify a product of numbers.
  • The question involves n written as a product, such as layouts of n tiles or grid sizes.
  • A single number up to about 10^12 needs analysis, where √n steps are affordable.

Check yourself

Answer each one in your head first, then open it.

How many divisors does 846 have?

12. Its factorization is 2^1 × 3^2 × 47^1, so the count is (1 + 1) × (2 + 1) × (1 + 1) = 12.

Why can't d = 4 divide rest when the loop reaches it?

Every factor of 2 was divided out while d was 2. If 4 divided rest, then 2 would too, which is impossible now.

Why does the bound use rest instead of the original n?

Only rest still needs factorizing. Its square root is smaller than n's, so the loop can stop much sooner, after 5 tries for 846 instead of 28.

Why is the leftover rest always prime when it's above 1?

It has no prime factor below d, and d * d > rest. A composite number always has a prime factor no bigger than its square root, so rest can't be composite.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps a promise at the top of each d: the product of factors times rest equals n, and rest has no prime factor smaller than d. At the start, factors is empty, rest is n, and there are no primes below 2, so the promise holds.

Each step keeps it. Dividing rest by d and pushing d keeps the product equal to n. The while loop only stops when d no longer divides rest, so after d++ there is still no prime factor below the new d. Every pushed d is prime: if it were composite, one of its smaller prime factors would divide rest, which the promise rules out.

The loop ends because d grows by 1 each time and rest never grows, so d * d > rest eventually; it takes at most about √n values of d. At that point, if rest were composite it would have a prime factor q with q * q <= rest < d * d, so q < d, which the promise forbids. So rest is 1 or a prime, and pushing it when it's above 1 completes the factorization, in ascending order.

Going deeper

3 more ideas

Why only primes get recorded

Suppose a composite d, like 6, divided rest. Then its prime factors 2 and 3 would also divide rest. But every 2 and 3 was already divided out when d was 2 and 3. So when the loop reaches a composite d, it can't divide rest, and only primes are ever pushed.

Why d * d <= rest is enough

If rest is composite, it is a × b with a <= b, so a × a <= rest. That means it has a factor no larger than its square root. If no d up to √rest divides it, it can't be composite, so it is 1 or prime.

Counting divisors from the factorization

If n = p1^a1 × p2^a2 × ..., every divisor picks an exponent from 0 to a1 for p1, from 0 to a2 for p2, and so on. So the number of divisors is (a1 + 1) × (a2 + 1) × .... For 360 = 2^3 × 3^2 × 5^1, that's 4 × 3 × 2 = 24 divisors.

Work it by hand

Every step in a table, with why

Factorize 846. It has a repeated factor and a large prime factor that the loop never reaches.

n = 846

Stepdd * drestfactorsWhat happensWhy
1--846[]startfactors is empty and rest holds the whole number.
224423[2]divide once846 % 2 === 0, so push 2 and set rest = 423. Then 423 % 2 is 1, so the while loop ends.
339141[2, 3]divide423 % 3 === 0, so push 3 and set rest = 141.
43947[2, 3, 3]divide againThe while loop tries 3 again: 141 % 3 === 0, so push another 3. Then 47 % 3 is 2, so it moves on.
541647[2, 3, 3]47 % 4 is 3: no4 can't divide rest: all the 2s are gone, and 4 is 2 × 2.
652547[2, 3, 3]47 % 5 is 2: no25 <= 47, so 5 is still worth trying. It doesn't divide.
763647[2, 3, 3]47 % 6 is 5: no6 is composite, and like 4 it can't divide rest. The loop tries it anyway because checking is cheap.
874947[2, 3, 3]49 > 47: loop endsNo number from 2 to 6 divides 47, and 47 has no factor larger than its square root without a matching smaller one.
9--47[2, 3, 3, 47]rest > 1: push itThe leftover rest is a prime, so it's the last factor.

It returns [2, 3, 3, 47], and 2 × 3 × 3 × 47 = 846. It tried only 5 divisors; the factor 47 was found without ever trying d = 47.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Prime factorizationO(√n)O(log n)Factorizing one number, or a few, up to about 10^12.
Trying every divisor up to nO(n)O(log n)Never needed: the square root bound gives the same answer with far fewer tries.
Smallest prime factor sieveO(n log log n)O(n)Factorizing many numbers below a fixed limit. Build the table once, then each number is factorized in O(log n).

Extra memory: O(log n): the factors list. Each factor is at least 2, so there are at most log₂ n of them, 20 for 2^20.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Prime factorization and the other approaches, on a scale where each line up is 10 times more steps.
  • Prime factorization O(√n)
  • Trying every divisor up to n O(n)
  • Smallest prime factor sieve O(n log log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Prime factorization3321,000
Trying every divisor up to n101,0001 million
Smallest prime factor sieve173,3174 million

Inputs that need care

5 tricky inputs
n = 1
The loop doesn't run (4 > 1) and rest > 1 is false, so it returns []. 1 has no prime factors, so that's correct.
n = 0 or a negative number like -12
It returns [] without looping, which hides the problem. Reject n < 2, or for negatives record -1 and factorize Math.abs(n).
A square of a prime: 49
At d = 7, 49 <= 49 is true, so 7 is divided out twice: [7, 7]. With < instead of <=, 49 would be returned as a single prime factor.
A large prime: 999999937
No d divides it, so the loop runs 31,621 times and then pushes 999999937 itself. Correct, but this is the slowest kind of input of its size.
A number past 2^53: 2 ** 53 + 2
JavaScript can't store it exactly, so the code factorizes a slightly different number and returns [2, 17, 858001, 308761441], whose product isn't the input. Use BigInt for numbers above 2^53.

Variations and follow-ups

Twists interviewers add

Skip even divisors

Divide out all the 2s first, then try only odd d with d += 2. That halves the number of tries: 999999937 needs 15,810 instead of 31,621. Trying only 6k ± 1 after 2 and 3 cuts it to a third.

Smallest prime factor table

When you must factorize many numbers up to a limit like 10^6, sieve once to store each number's smallest prime factor. Then each factorization is a few lookups and divisions, O(log n) each.

Counting or summing divisors

Group the factors into prime powers, 846 = 2^1 × 3^2 × 47^1. The number of divisors is (1 + 1) × (2 + 1) × (1 + 1) = 12. The sum of divisors multiplies 1 + p + p^2 + ... for each prime.

Very large numbers

For numbers near 10^18, √n is a billion, too many tries. Programs first test whether the number is prime with Miller-Rabin, then split it with Pollard's rho method, using BigInt.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "count the divisors", "is this number a product of only 2, 3, and 5", "smallest number with this many factors", "largest prime factor", or any question about what a number is made of.
  • Explain it as: "I divide out 2 as many times as I can, then 3, and so on. Any d that still divides is prime, because its smaller factors are gone. I stop at √rest, and anything left over is a prime."
  • Test 1, a prime, a prime squared like 49, and a number with a big prime factor like 846. The last two catch the <= mistake and the missing final push.
  • A common follow-up is "what if you have a million numbers to factorize?" Answer with the smallest-prime-factor sieve: one O(n log log n) pass, then O(log n) per number.

Where frontend code uses it

The same idea in real UI code
  • Laying out n thumbnails in a near-square grid means finding the factor pair of n closest to √n, such as 12 = 3 × 4 instead of 2 × 6.
  • Simplifying a ratio, such as image dimensions, can be done by cancelling shared prime factors, though the GCD does it faster.
  • Number-theory widgets in education apps show factor trees, which are exactly the trial division steps.

Related algorithms