Factor Tree Game
Factor pairs always straddle √n, so checking only up to √n — and only at prime candidates — finds every prime factor.
A complete interactive classroom, not just a preview.
Start when you are ready to enter this Stage's 4 scenes and explore, respond, and learn as you go.
How can you split a big number into primes without checking every single number?
A classmate hands you the number 60 and challenges you to break it into a 'rainbow stack' of prime building blocks as fast as possible.
Trying every number from 2 upward feels endless — will you run out of time before you split it all the way down?
A split-screen simulation showing naive checking versus the √n shortcut, with factor pairs lighting up as matching dots on a number line.
Stop checking once a factor exceeds √n, because every factor has a partner across the square root, so the rest are already accounted for.
- writing formal proofs
- non-trial-division algorithms like Fermat or Pollard rho
- factoring numbers above four digits
- 01The 60 ChallengeslideSlot 1Hook
Two kids race to factor 60; one checks every number, the other stops halfway. Who finishes first, and why?
- Goal: break 60 into prime pieces
- Slow way: test 2, 3, 4, 5, … all the way up
- Fast way: stop early and still win
PhenomenonTwo racers factor 60; the faster one barely checks half the numbers the slower one does.
QuestionHow can the faster racer be sure no prime factor was missed?
- 02Where Should You Stop?slideSlot 2Tension
Predict the smallest number you must check to fully factor 97 — a number that turns out to be prime.
- Prediction: how far up must you test 97?
- Tempting answer: all the way to 96
- Surprise: a much shorter trip is enough
PredictionTo factor 97, what is the smallest range of trial divisors you must check?
Tempting intuitionMost learners assume you must test every number below n.
- 03Factor Pair ExplorerinteractiveSlot 3Reveal
Drag the slider to set n and watch factor pairs pop up on a number line; any pair with the small partner > √n proves checking past √n is wasted work.
- Factors always come in pairs: d × (n/d)
- The smaller member of every pair sits at or below √n
- So √n is a complete checkpoint
EvidenceInteractive number line where factor pairs light up as matching dots symmetric about √n.
ConclusionStop the trial-division search at √n and you cannot miss a prime factor.
Mechanism- 1If d divides n, then n/d also divides n — factors arrive in pairs
- 2For any pair, the smaller member is ≤ √n and the larger is ≥ √n
- 3Testing only the small members up to √n already covers every factor
- 04Your Factor Tree StrategyslideSlot 4Takeaway
Apply the √n rule to a new number, 132, and see the factor tree stop early while still reaching prime leaves.
- New target: 132
- Check primes only, stop once p × p > 132
- Factor tree lands on 2 × 2 × 3 × 11
TransferNow that you know factors come in pairs around √n, factor 132 using only prime trial divisors up to its square root.
Expected inference132 splits into 2 × 2 × 3 × 11, and no trial divisor above 11 was needed.
Discussion threads for a Stage aren't available yet.
