문제 개요
두 개의 숫자가 주어졌을 때, 첫 번째 숫자가 두 번째 숫자의 모든 소인수로 나누어 떨어지는지 확인하는 문제입니다. 예를 들어 첫 번째 숫자가 120이라면 소인수는 {2, 3, 5}입니다. 두 번째 숫자가 75라면 소인수는 {3, 5}입니다. 이 경우 120은 3과 5로 모두 나누어 떨어지므로 정답은 "예"가 됩니다.
알고리즘 접근 방법
이 문제는 최대공약수(GCD)와 재귀 호출을 활용하면 효율적으로 해결할 수 있습니다. 핵심 로직은 다음과 같습니다.
- 두 번째 숫자가 1이면 소인수가 존재하지 않으므로 항상 참(True)을 반환합니다.
- 두 수의 최대공약수(GCD)를 구합니다. GCD가 1이라면 두 수는 서로소 관계이므로 거짓(False)을 반환합니다.
- GCD가 1보다 크다면, GCD에 포함된 소인수들은 첫 번째 숫자 x 역시 나눌 수 있습니다.
- 남은 소인수까지 모두 확인하기 위해, 두 번째 숫자를 GCD로 나눈 값(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
위 실행 결과는 "120은 75의 모든 소인수로 나누어 떨어질 수 있다"는 의미입니다. 이 알고리즘은 매 단계마다 두 번째 숫자를 GCD로 계속 나누어 줄이기 때문에, 소인수를 일일이 찾아내는 방식보다 훨씬 간결하고 빠르게 동작한다는 장점이 있습니다.