De ce contează?
Imaginează-ți că vrei să afli dacă un colectiv de elevi se poate aranja perfect în rânduri egale (mai mult de un rând, cu mai mult de un elev pe rând). Dacă 12 elevi: merge — 3 rânduri de câte 4. Dacă 13 elevi: orice aranjare egală eșuează, rămâne mereu cineva pe dinafară. Numerele care NU se pot aranja decât într-un singur rând lung sunt exact numerele prime.
Intuiția
Un număr n ≥ 2 este prim dacă singurii lui divizori sunt 1 și n însuși.
Altfel spus, nu există niciun număr între 2 și n-1 care să-l împartă exact.
Ca să verifici, încerci pe rând să-l împarți la 2, 3, 4, ... și vezi dacă
vreunul „intră fără rest". Dacă găsești fie și un singur divizor, numărul e
compus; dacă niciunul nu intră, e prim.
Cheia eficienței: divizorii vin mereu în perechi. Dacă d împarte pe n, atunci
și n/d îl împarte — iar dintre cei doi, unul este mereu mic (sub radical), iar
celălalt mare (peste radical). Deci e de ajuns să cauți doar partenerul mic.
Pentru n = 36: perechile de divizori sunt 1·36, 2·18, 3·12, 4·9, 6·6.
Toate sunt „oglindite" în jurul lui 6 = radical din 36. Dacă n-ai găsit niciun
divizor până la 6, nu mai există niciunul nici deasupra — partenerul mare l-ar
fi adus pe cel mic.