De ce contează?
Vrei să așezi 29 de bomboane în cutii dreptunghiulare, perfect pline, cu mai mult de un rând. Încerci: 2 rânduri? Nu iese egal. 3 rânduri? Nici. Oricât te chinui, singura aranjare perfectă e un singur rând lung de 29. Un număr care „refuză" orice împărțire în rânduri egale (în afară de 1 și el însuși) se numește prim. 29 este prim.
Intuiția
Un divizor al lui n este un număr care îl împarte exact, fără rest. Orice
număr se împarte măcar la 1 și la el însuși. Un număr prim este unul care
nu are alți divizori în afară de aceștia doi — adică are exact doi divizori.
Deci „este n prim?" se traduce în „are n vreun divizor între 2 și n-1?".
Dacă da, nu e prim. Dacă nu găsim niciunul, e prim.