Cerinţa

Se dau două numere naturale nenule. Să se verifice dacă cele două numere au exact aceiași factor primi, indiferent de puterea acestora.

Date de intrare

Programul citește de la tastatură numerele n și m.

Date de ieşire

Programul afișează pe ecran mesajul DA, dacă cele două numere au exact aceiași factori primi, respectiv NU în caz contrar.

Restricţii şi precizări

• cele două numere citite vor fi mai mici decât 2 ³⁰

Exemplu 1:

Intrare

72 48

Ieșire

DA

Explicație

72 și 48 au exact aceiași factori primi: 2 3.

Exemplu 2:

Intrare

72 30

Ieșire

NU

Explicație

Factorii primi ai lui 72 sunt 2 3, iar factorii primi ai lui 30 sunt 2 3 5.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    bool aceiasi_factori = true;
    int d = 2;
    while(a > 1){
        int p = 0;
        if(a % d == 0){
            if(b % d != 0){
                aceiasi_factori = false;
            }
            while(a % d == 0)
                a /= d;
            while(b % d == 0)
                b /= d;
        }
        d++;
        if(d * d > a)
            d = a;
    }
    if(aceiasi_factori && b == 1)
        cout << "DA";
    else
        cout << "NU";
    return 0;
}