In tất cả các số có tập thừa số nguyên tố là tập con của tập hợp các thừa số nguyên tố của X trong C ++

Trong bài toán này, chúng ta được cho một tập hợp N số và một số X. Và chúng ta phải in tất cả các số từ mảng có tập hợp các thừa số nguyên tố là tập con của tập hợp thừa số nguyên tố của X.

Hãy lấy một ví dụ để hiểu vấn đề

Input: X= 30 , array = {2, 3, 6, 10, 12}
Output : 2 3 6

Để giải quyết vấn đề này, chúng ta phải duyệt các phần tử của mảng. Và chia phần tử này với gcd của (phần tử, x). Lặp lại phép chia cho đến khi gcd trở thành 1. Và in số còn lại.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void printPrimeSet(int a[], int n, int x){
   bool flag = false;
   for (int i = 0; i < n; i++) {
      int num = a[i];
      int g = __gcd(num, x);
      while (g != 1) {
         num /= g;
         g = __gcd(num, x);
      }
      if (num == 1) {
         flag = true;
         cout<<a[i]<<" ";
      }
   }
   if (!flag)
      cout << "There are no such numbers";
}
int main(){
   int x = 60;
   int a[] = { 2, 5, 10, 7, 17 };
   int n = sizeof(a) / sizeof(a[0]);
   cout<<"Numbers whose set of prime numbers is subset of set of prime factor of "<<x<<"\n";
   printPrimeSet(a, n, x);
   return 0;
}

Đầu ra

Các số có tập hợp số nguyên tố là tập hợp con của tập hợp thừa số nguyên tố là 60

2 5 10