Descompunerea in factori primi a unui numar in C++

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 = 2³ * 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:

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