Factor Race
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 far must a player check to guarantee every prime factor of a number is found?
Two players race to break 60 into prime pieces: one tests every number from 2 to 59, the other quits halfway and still wins.
How can the player who checks half as many numbers be sure nothing was missed?
A factor-pair slider showing every pair's small partner landing at or below √n, paired with a side-by-side factor tree that finishes before the brute-force racer.
Factor pairs always straddle √n, so checking only prime candidates up to √n finds every prime factor — the racer's shortcut is safe.
- general divisibility rules
- factoring polynomials
- largest prime factor algorithms beyond trial division
- 01The 60 DuelslideSlot 1Hook
Player A tests every number from 2 to 59 to break 60 into primes. Player B quits after testing only a handful. The buzzer sounds and Player B's board is complete.
- Goal: split 60 into prime factors
- Player A tests 2, 3, 4, 5, … all the way up
- Player B stops early and still wins — but how?
PhenomenonTwo players race to prime-factor 60; the winner checked barely half the numbers the loser did.
QuestionHow can the faster player be sure no prime factor was skipped?
- 02How Far Up Must You Check?slideSlot 2Tension
Predict the shortest search range that still guarantees a complete prime factorization of 97. The number is prime — so where is the safe stopping point?
- New target: the prime number 97
- Most players assume you must test all 96 numbers below it
- A much shorter trip is enough — name the limit
PredictionWhat is the smallest range of trial divisors that fully factors 97?
Tempting intuitionMost players assume you must test every integer from 2 up to n−1.
- 03Factor Pair ArenainteractiveSlot 3Reveal
Set n and the search limit, then watch factor pairs pop up as matching dots symmetric about √n. The slider proves that once the limit crosses √n, no new factor can appear.
- Factors always arrive in pairs: d × (n/d)
- The smaller partner of every pair sits at or below √n
- So √n is a complete checkpoint for the race
EvidenceInteractive number line where factor pairs light up as matching dots symmetric about √n, and the search-limit marker sweeps left to right.
ConclusionStop the trial-division search at √n and you cannot miss a prime factor — Player B's shortcut is safe.
Mechanism- 1If d divides n, then n/d also divides n — factors come in pairs
- 2For any pair, the smaller member is ≤ √n and the larger is ≥ √n
- 3Testing only the small partners up to √n already covers every factor
- 04Win the Round: Factor 132slideSlot 4Takeaway
Apply the √n rule as Player B against a fresh opponent: factor 132 using only prime trial divisors up to its square root, and show the factor tree closing out early.
- New round, new target: 132
- Check primes only, stop once p × p > 132
- Factor tree lands on 2 × 2 × 3 × 11
TransferNow that factor pairs straddle √n, run the race again on 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 ever needed.
Discussion threads for a Stage aren't available yet.
