fbpx

Algoritm pentru determinarea divizorilor primi ai unui numar in C++

0

Problema: Se citeste de la tastatura un numar natural n. Sa se afiseze toti divizorii primi ai acestui numar.

Haideti mai intai sa dam un exemplu. Pentru n = 24 avem divizorii primi 2 si 3 (deoarece 24 = 23 * 3).

Divizor prim

Definitie: Un numar x este divizor al altui numar y, daca y se poate scrie ca produsul dintre x si un alt numar intreg t. In plus, daca x este un numar prim, acesta se numeste divizor prim al numarului y.

Mai multe despre divizori: Divizor – Wikipedia

Daca doresti in schimbi sa aflii toti divizorii unui numar, un algoritm mai usor este acesta: Algoritm pentru afisarea divizorilor unui numar

Algoritm pentru afisarea divizorilor primi ai unui numar

Incepem sa cautam divizorii posibili ai unui numar. Asa ca incepem cu 2.

Repetam urmatorii pasi atat timp cat numarul nostru este mai mare decat 1:

  • Daca numarul se imparte exact la divizorul curent
    • Se va impartii numarul la divizor de cate ori este posibil. Pentru fiecare data cand aceasta impartire este posibila, incrementam „putere”
    • Se afiseaza divizorul si puterea divizorului
  • Se incrementeaza divizorul.

Urmarind pas cu pas algoritmul:

Numar Divizor Putere
 24  2  0
 12  2  1
 6  2  2
 3  2  3
 3  3  0
 1  3  1
 0 4  0

Algoritmul acesta se poate optimiza foarte mult folosind Ciurul lui Eratostene, dar o sa discutam despre asta intr-un tutorial viitor.

Comentarii
Se incarca comentariile...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More