c++ Hai số tự nhiên được gọi là nguyên tố tương đương nếu chúng có chung các ước số nguyên tố. Ví dụ như các số 75 và 15 là nguyên tố tương đương vì cùng có các ước nguyên tố là 3 và 5. Cho trước hai s...

#include <iostream>
#include <set>
#include <cmath>

std::set<int> phanTichThuaSoNguyenTo(int n) {
   std::set<int> uocSoNguyenTo;
   if (n < 2) {
       return uocSoNguyenTo;
   }
   int d = 2;
   int temp = n;
   while (d * d <= temp) {
       if (temp % d == 0) {
           uocSoNguyenTo.insert(d);
           while (temp % d == 0) {
               temp /= d;
           }
       }
       d++;
   }
   if (temp > 1) {
       uocSoNguyenTo.insert(temp);
   }
   return uocSoNguyenTo;
}

bool kiemTraNguyenToTuongDuong(int m, int n) {
   if (m < 2 || n < 2) {
       return false;
   }
   std::set<int> uocSoNguyenToM = phanTichThuaSoNguyenTo(m);
   std::set<int> uocSoNguyenToN = phanTichThuaSoNguyenTo(n);
   return uocSoNguyenToM == uocSoNguyenToN;
}

int main() {
   int m, n;
   std::cout << "Nhap so tu nhien M: ";
   std::cin >> m;
   std::cout << "Nhap so tu nhien N: ";
   std::cin >> n;

   if (kiemTraNguyenToTuongDuong(m, n)) {
       std::cout << m << " va " << n << " la nguyen to tuong duong." << std::endl;
   } else {
       std::cout << m << " va " << n << " khong la nguyen to tuong duong." << std::endl;
   }

   return 0;
}