De ce contează?
Ai o sumă de plătit și doar bancnote „indivizibile": dai cât poți în bancnote de 2, apoi în cele de 3, apoi în cele de 5 și tot așa, din cea mai mică spre cea mai mare. La final ai un teanc unic — exact aceleași bancnote, oricine ar număra. La fel, orice număr natural mai mare decât 1 se „rupe" într-un produs unic de numere prime: cărămizile din care e construit. A-l descompune înseamnă să-i numeri cărămizile.
Intuiția
Orice număr mai mare decât 1 se scrie în mod unic ca produs de numere prime
(teorema fundamentală a aritmeticii). De exemplu 360 este 2 * 2 * 2 * 3 * 3 * 5,
adică 2^3 * 3^2 * 5. A descompune un număr înseamnă să-i găsești aceste cărămizi.
Ideea de bază e simplă: începi cu cel mai mic divizor posibil și îl scoți din
număr cât timp mai poți, apoi treci la următorul.
Cheia e ordinea: pornești de la cel mai mic divizor și îl scoți complet cât
timp divide, abia apoi treci mai departe. Atunci orice d care încă divide
numărul redus e automat prim — toți factorii mai mici decât el au fost deja
scoși, deci d nu mai poate fi compus. Nu trebuie să verifici primalitatea
nimănui.