Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

소인수 집합이 C++에서 X의 소인수 집합의 하위 집합인 모든 숫자 인쇄


이 문제에서 N개의 숫자 집합과 숫자 X가 주어집니다. 그리고 배열에서 소인수 집합이 집합의 하위 집합인 모든 숫자를 인쇄해야 합니다. X의 소인수.

문제를 이해하기 위해 예를 들어보겠습니다.

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

이 문제를 해결하려면 배열의 요소를 탐색해야 합니다. 그리고 이 요소를 gcd로 나눕니다. (요소, x)의. gcd가 1이 될 때까지 나눗셈을 반복하고 나머지 숫자를 출력합니다.

예시

#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;
}

출력

소수의 집합이 60의 소수 집합의 부분집합인 숫자

2 5 10