Lectia 15

Descompunerea unui numar in factori primi

Orice număr natural nenul, care nu este număr prim poate fi scris ca un produs de numere naturale prime. Scrierea unui număr natural ca un produs de numere naturale prime se numeşte descompunere în factori primi a numărului natural respectiv. Exemple:

Deci 24200= 2³*5²*11²

Algoritmul care determină descompunerea în factori primi a numărului natural n are următoarea formă:

citeşte n (număr natural) // numărul care se va descompune în factori primi

scrie ”Numărul ”, n, ” descompus în factori primi este egal cu: ”

d = 2 // primul factor la care incercăm sa împărţim pe n

┌cât timp n>=1 execută

│ s=0 //număr de câte ori factorul d îl divide pe n

│ ┌cât timp n%d=0 execută

│ │ s=s+1

│ │ n=n/d

│ └■

│ ┌dacă s ≠ 0 atunci

│ │ scrie d,” la puterea ”, s

│ └■

│ d=d+1

└■