Question

Buna!
Ma puteti ajuta va rog cu aceasta problema, de pe pbinfo?

#435 FactoriPrimi
Clasa a 9-a Algoritmi elementari Divizibilitate FactoriPrimi
Etichete: Descompunere in factori


Enunț
Blockly
Soluții
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 30
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.

Multumesc!

Answer 1

Răspuns:

#include <iostream>

using namespace std;

long long n,m,nr1=1,nr2=1;

int main()

{

   cin >> n >> m;

   long long d;

   d=2;

   while (d*d<=n)

   {

       int e=0;

       while (n%d==0)

       {

           n=n/d;

           ++e;

       }

       if (e>0) nr1=nr1*d;

       ++d;

   }

   if (n>1) nr1=nr1*n;

   d=2;

   while (d*d<=m)

   {

       int e=0;

       while (m%d==0)

       {

           m=m/d;

           ++e;

       }

       if (e>0) nr2=nr2*d;

       ++d;

   }

   if (m>1) nr2=nr2*m;

   if (nr1==nr2) cout << "DA";

   else cout << "NU";

}

Explicație:

creez două numere formate din produsul divizorilor primi a numerelor fără repetări.

nr1 pentru n,  nr2 pentru m.

dacă numerele formate astfel sunt egale, atunci OK...