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

#include    <iostream>

using namespace std;

int main()
{
    int numar, putere;

    cin >> numar;

    int divizor = 2;
    while (numar > 1)
    {
        if(numar % divizor == 0) // Daca numarul se imparte exact la divizor
        {
            putere = 0;
            while(numar % divizor == 0)
            {
                putere = putere + 1;
                numar = numar / divizor;
            }
            cout << divizor << " la puterea " << putere << "\n";
        }
        divizor++;
    }
    return 0;
}

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