Repeated Division Method

Repeated Division Method | CodeSignal Learn

Introduction

1

A Different Route to the Same Primes

1

How Repeated Division Works

1

Worked Example: Factorising 72

72

A Larger Example: Factorising 180

180

Key Details to Remember

2

Choosing Between Factor Trees and Repeated Division

2

Conclusion and Next Steps

1

Previous Lesson Next Lesson: Using Index Notation

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Welcome back to Breaking Numbers Into Primes! This is our third lesson out of four, which means we are well past the halfway mark. So far, we have built a solid foundation: in lesson one, we learned what prime factorisation means and why every number greater than $1$ has a unique prime "fingerprint"; in lesson two, we put that knowledge to work by constructing factor trees that visually split numbers into primes, branch by branch. Today, we pick up a second technique — repeated division — that reaches the same set of primes through a more streamlined, column-based approach. By the end of this lesson, we will also develop some intuition for when each method shines brightest.

Factor trees are wonderful for seeing how a number breaks apart, but as numbers grow larger, those branches can sprawl across the page and become difficult to track. Repeated division offers a tidier alternative: instead of branching outward, we work straight down a single column, dividing by one small prime at a time until nothing is left to divide. Think of it like peeling layers off an onion — each division strips away one prime factor, and when the onion is fully peeled (the quotient reaches $1$ ), every layer is sitting in a neat stack beside it.

The result is always the same unique set of prime factors we would find with a factor tree — the Fundamental Theorem of Arithmetic guarantees that. The difference is only in how we get there.

The method follows a simple loop. We start with the number we want to factorise, divide it by the smallest prime that goes into it evenly, and write down the quotient. Then we take that quotient and do it all again. We keep going until the quotient reaches $1$ , which tells us every prime factor has been extracted.

Start with the composite number.
Find the smallest prime that divides it evenly — try $2$ , then $3$ , then $5$ , then $7$ , and so on.
Divide and record the quotient.
Repeat steps 2–3 with the new quotient.
Stop when the quotient equals $1$ .

The primes we used as divisors, read from first to last, give the complete prime factorisation. Because we always begin with the smallest applicable prime, the factors come out in ascending order automatically — no sorting needed at the end.

Flowchart of the repeated division algorithm showing decision steps for choosing a prime divisor and stopping when the quotient reaches 1

Let's factorise $72$ using repeated division. Since $72$ is even, the smallest prime that divides it is $2$ , so that is where we begin.

Prime	Division	Quotient
$2$	$72 \div 2$	$36$
$2$	$36 \div 2$	$18$
$2$	$18 \div 2$	$9$
$3$	$9 \div 3$	$3$
$3$	$3 \div 3$	$1$

Division ladder diagram for factorising 72 by repeated division, showing five rows with primes 2, 2, 2, 3, 3 on the left and quotients 36, 18, 9, 3, 1 descending on the right

We divide by $2$ three times, bringing us from $72$ to $36$ to $18$ to $9$ . Once the quotient is odd, $2$ no longer works, so we move to the next prime, $3$ . Dividing $9$ by $3$ gives $3$ , and dividing that $3$ by $3$ gives $1$ . We stop here and read the primes from the left column:

72 = 2 \times 2 \times 2 \times 3 \times 3

Quick check: $2 \times 2 \times 2 = 8$ and $3 \times 3 = 9$ , so $8 \times 9 = 72$ ✓.

Now let's try $180$ , a number that would produce quite a wide factor tree. With repeated division, the layout stays compact.

Prime	Division	Quotient
$2$	$180 \div 2$	$90$
$2$	$90 \div 2$	$45$
$3$	$45 \div 3$	$15$
$3$	$15 \div 3$	$5$
$5$	$5 \div 5$	$1$

After two divisions by $2$ , the quotient $45$ is odd, so we move to $3$ . After two divisions by $3$ , the quotient $5$ is not divisible by $3$ , so we advance to the next prime, $5$ . One final division brings us to $1$ .

180 = 2 \times 2 \times 3 \times 3 \times 5

Check: $4 \times 9 \times 5 = 36 \times 5 = 180$ ✓. Five clean rows, no branches to track, and the factors appeared in ascending order without any extra effort.

A few practical points will help keep repeated divisions accurate and efficient. The divisibility rules from the previous course (Divisibility Shortcuts) are especially handy here — for instance, checking whether the last digit is even to test for $2$ , or summing the digits to test for $3$ .

Always start with the smallest prime. Beginning with $2$ (if the number is even) and working upward ensures we never skip a factor and that our list stays in order.
Stay with the same prime until it no longer divides evenly, then move to the next prime. This keeps the work organised and makes counting repeated factors simple.
Always end at $1$ . Stopping at a quotient like $6$ instead of continuing means some prime factors are still hiding inside. A quotient of $1$ is the only valid signal that every prime has been extracted.
Verify by multiplying back. Multiply all the prime divisors together — the product must equal the original number.

With two methods in our toolkit, a natural question arises: which one should we pick? Both always work and both produce the same answer, but each has situations where it feels more natural.

	Repeated Division	Factor Trees
Works best when	The number has many small prime factors ( $2$ s, $3$ s, $5$ s)	We can spot a useful factor pair right away
Layout	Compact, single column	Visual, branching diagram
Starting point	Always begin with the smallest prime	Any factor pair we like
Strength	Removes guesswork; very systematic	Flexible; shows structure at a glance

Side-by-side illustration of a factor tree and a repeated division ladder both factorising 72, converging on the same prime factorisation

Consider a number like $360$ : it is loaded with small prime factors ( $2^3 \times 3^2 \times 5$ ), so repeated division lets us peel them off quickly in a tidy column. Now consider $91$ : at first glance it has no obvious small factor, but if you happen to notice that $91 = 7 \times 13$ , a factor tree finishes in a single split. In practice, many problem-solvers blend both approaches — for example, spotting that $84 = 12 \times 7$ , noting the prime $7$ , and then switching to repeated division to finish off $12$ . The best method is simply whichever one helps you work accurately and with confidence.

In this lesson, we added repeated division to our prime factorisation toolkit. The process is beautifully systematic: divide by the smallest applicable prime, record the quotient, and continue until the quotient is $1$ . We also compared the method side by side with factor trees, so we can now make an informed choice about which approach suits a given number best.

Time to put these skills into action! In the practice exercises that follow, you will complete a partially filled division layout, factorise numbers on your own using repeated division, tackle a larger challenge with more prime factors, and sharpen your judgement about when to reach for each method. Let's see how quickly those primes line up!