Naar de inhoud
OneKitly

Proving a Million Is Prime Takes a Thousand Divisions, Not a Million

Gepubliceerd op 16-11-2026 · 3 min leestijd · Dagelijkse calculators

Lena Hoffmann

Lena Hoffmann — Redacteur wetenschap en onderwijs bij OneKitly

Wiskunde · Natuurkunde

Getoetst aan 2 bronnen

Profiel bekijken →
Kort gezegd

To test whether a number has a factor, you never have to look past its square root. If a number splits into two factors, one of them is at or below the square root and the other at or above it, so finding nothing small means there is nothing at all. Checking 1 000 003 therefore needs trial divisions only up to 1000, and it survives every one of them: it is prime. Its neighbour 1 000 001 falls quickly, because 101 divides it exactly, leaving 9901. The square root is what turns an impossible search into an afternoon's work, and it is the first thing anyone writing a primality test discovers.

Advertentie

1 000 003 is prime and the proof stops at 1000, its square root. 1 000 001 is not, and the search ends at the third try: 101 divides it.

Only the primes need trying

Dividing by 4 is wasted effort if 2 already failed, so the list of candidates is not the thousand numbers below the square root but the 168 primes among them. That alone cuts the work by six, and skipping even numbers and multiples of three catches most of the rest almost for free. The classic implementation checks 2, then 3, then every number of the form six-either-side-of-a-multiple-of-six, which covers every possible prime and tests only a third of the integers.

Why the trick stops helping

Halving the number of digits sounds like a lot until the number is long. The square root of a 600-digit number still has 300 digits, so trial division on the keys used by modern cryptography would need more operations than there are atoms in the observable universe. Real primality testing therefore abandons division entirely and uses probabilistic tests that give a wrong answer with a probability that can be pushed below any threshold you name. Those tests prove a number is composite far more easily than they exhibit a factor, which is exactly the asymmetry the security rests on.

Work needed to test a number by trial division
NumberDivisions to tryResult
1 000 0013 before it fails101 × 9901
1 000 003168 primes up to 1000Prime
A 600-digit numberMore than atoms in the universeUnusable
PriemgetalcontroleKijk na of een getal een priemgetal is en vind zijn kleinste deler.Probeer de tool →
Advertentie

Veelgestelde vragen

Why is 1 not prime?
By decision, to keep factorisation unique. If 1 counted, then 12 could be written as 2×2×3, or 1×2×2×3, or 1×1×2×2×3, and the statement that every number has exactly one prime factorisation would need an exception clause. Nineteenth-century tables did list 1 as prime, and the convention changed because every theorem was cleaner without it. Definitions in mathematics are chosen for consequences rather than discovered, and this is the clearest small example.
How do I test a number by hand?
Take the square root, round up, and divide by every prime up to it. For anything under ten thousand that is at most 25 divisions, most of which are dismissed instantly: even numbers fail on 2, digit sums divisible by three fail on 3, anything ending in 0 or 5 fails on 5. What survives to be tested seriously is a short list. Above a million the method becomes tedious rather than difficult, which is exactly the moment to hand it to a machine.

Artikelen die je misschien interesseren

Alle gidsen →

Vergelijkbare tools

Bronnen

Een fout in dit artikel gezien?