C++에서 숫자가 다른 숫자의 모든 소수로 나누어 떨어지는지 확인하십시오.

두 개의 숫자가 있다고 가정합니다. 어떤 숫자가 모든 소인수로 나누어 떨어지는지 아니면 두 번째 숫자로 나누어 떨어지는지 확인해야 합니다. 숫자가 120이라고 가정합니다. 소인수는 {2, 3, 5}이고 다른 수는 75이며 여기에서 소인수는 {3, 5}입니다. 120도 3과 5로 나눌 수 있으므로 결정은 yes입니다.

하나의 숫자가 1이면 소수가 없으므로 답은 참입니다. 그렇지 않으면 이 두 숫자의 GCD를 찾아야 합니다. GCD가 1이면 공소수입니다. 따라서 대답은 거짓입니다. GCD가> 1이면 GCD에는 x도 나누는 소수 제수가 포함됩니다(x는 첫 번째 숫자로). 두 번째 숫자 y / GCD에 고유한 소수가 있는 경우 모든 고유한 소수가 있는 경우. 재귀를 사용하여 쌍(x, y/GCD)에 대한 고유성을 찾아야 합니다.

예시

#include <iostream>
#include <algorithm>
using namespace std;
bool isDivisible(int a, int b) {
   if (b == 1)
      return true;
   int gcd = __gcd(a, b);
   if (gcd == 1)
      return false;
      return isDivisible(a, b / gcd);
}
int main() {
   int a = 120, b = 75;
   if (isDivisible(a, b))
      cout << a << " can be divisible by all prime factors of " << b;
   else
      cout << a << " can NOT be divisible by all prime factors of " << b;
}

출력

120 can be divisible by all prime factors of 75