Numere prime intre ele in C++

Definitie numere prime intre ele

În matematică, două numere întregi sunt prime între ele dacă ele nu au alt factor comun în afară de 1, sau, altfel spus, dacă cel mai mare divizor comun al lor este 1. Algoritmul lui Euclid reprezintă o metodă rapidă de a afla dacă două numere sunt sau nu prime între ele.

Sursa: wikipedia.com

De exemplu numerele 8 si 9. Aceste numere nu sunt prime (deoarece 8 se imparte la 4 iar 9 se imparte la 3). Insa numerele 8 si 9 sunt numere prime intre ele. Un mic sfat: oricare doua numere consecutive sunt prime intre ele.

Algoritm de verificare a numerelor prime intre ele

Urmam exact definitia matematica de mai sus. Vom folosii functia recursiva din Algoritmul lui Euclid pentru a ne usura munca.

#include    <iostream>

using namespace std;

int GCD(int A, int B)
{
    if(!B)
        return A;
    return GCD(B, A%B);
}

int main()
{
    int A, B;
    cin >> A >> B;

    if(GCD(A, B) == 1)
        cout << "Cele doua numere sunt prime intre ele";
    else
        cout << "Cele doua numere NU sunt prime intre ele.";

    return 0;
}