Download Algoritmi elementari PDF

TitleAlgoritmi elementari
File Size910.0 KB
Total Pages5
Document Text Contents
Page 3

Descompunerea unui număr în factori primi

n=12 n=150 n=28 Observații

n d
12 2
6 2
3 3
1

n d
150 2
75 3
25 5
5 5
1

n d
28 2
14 2
7 7
1

- Primul factor prim posibil este d2
- Se descompune numărul în factori primi până când

devine 1 sau cât timp este ≠1 (cât timp n≠1)
- Pentru fiecare factor prim d, se împarte numărul la d,

atâta timp cât este posibil (cât timp n%d=0)
- Când n nu se mai împarte la d, se trece la următorul

factor prim (dd+1)

Algoritmul în pseudocod

d2 //primul factor prim posibil
cât timp n≠1 execută
p0 //puterea la care apare factorul prim
cât timp n%d=0 execută //se împarte n la d cât timp este posibil
pp+1
n[n/d]

dacă p≠0 atunci
scrie d,’ ‘

dd+1



d2
repetă
p0
cât timp n%d=0 execută
pp+1
n[n/d]

dacă p≠0 atunci
scrie d,’ ‘

dd+1
≠ până când n=1

Page 4

http://ro.wikipedia.org/wiki/Prime_%C3%AEntre_ele
http://ro.wikipedia.org/wiki/Numere_prime

Similer Documents