Divizibilitate

Divizorii unui număr

Un prim algoritm banal este verificarea tuturor numerelor până la n.

Implementare

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    for (int d = 1; d <= n; d++) {
        if(n % d == 0) {
            cout << d << " ";
        }
    }

    return 0;
}

O variantă mai eficientă este să verificăm toate numerele până la radicalul numărului n și să le grupăm pe perechi. Pentru numărul 12 vom avea următoarele cazuri:

• 1 face pereche cu 12
• 2 face pereche cu 6
• 3 face pereche cu 4
• 4 * 4 > 12, deci ne oprim

Implementare

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    for (int d = 1; d * d <= n; d++)
        if(n % d == 0) {
            cout << d << " ";

            if(d * d < n) {
                cout << n / d << " ";
            }     
        }

    return 0;
}

Se observă că am evitat folosirea funției sqrt(n), care poate fi ineficientă și inexactă, folosind condiția d * d <= n, care se poate traduce prin d <= sqrt(n).

Algoritmul lui Euclid

Algoritmul lui Euclid ne ajută să determinăm CMMDC-ul dintre 2 numere. Acesta are la bază ideea că CMMDC-ul dintre 2 numere divide și restul împărțirii acestora.

Implementare

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;

    while(b != 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    cout << a;

    return 0;
}

Dacă cunoastem CMMDC-ul unui număr, îi putem afla imediat și CMMMC-ul, cu ajutorul formulei (a, b) * [a, b] = a * b, unde (a, b) este CMMDC, iar [a, b] este CMMMC. Deci [a, b] = a * b / (a, b).

Numere prime

• Un număr natural p > 1 se numște prim dacă p|ab ⇒ p|a sau p|b.
• Un număr natural p > 1 se numește ireductibil dacă d|p ⇒ d = 1 sau d = p.
• Un număr natural p > 1 dacă și numai dacă este ireductibil.
• Numerele 0 și 1 nu pot fi prime.

Pentru a demonstra că un număr natural este prim, putem demonstra că acesta nu are alți divizori în afară de 1 și el însuși.

Implementare

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    bool prime = true; // presupunem inițial ca n este prim

    if (n < 2) {
        prime = false; // dacă n este mai mic de 2, nu este prim
    }

    for (int d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            prime = false; // dacă am găsit un divizor, n nu este prim
        }
    }

    if (prime) {
        cout << n << " este prim";
    }
    else {
        cout << n << " nu este prim";
    }
        
    return 0;
}

Descompunerea în factori primi

Implementare

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int d = 2;
    while (n > 1) {

        int count = 0;
        while (n % d == 0) {
            n /= d;
            count++; // dacă d este divizorul lui n, creștem numărătoarea
        }

        if (count) {
            cout << d << ' ' << count << '\n';
        }

        d++;
    }

    return 0;
}

Programul de mai sus afișează descompunerea în factori primi a lui n sub formă de factor putere.