두 수의 최대공약수(GCD)는 두 수를 나누는 가장 큰 수입니다.
예:45와 27이라는 두 개의 숫자가 있다고 가정해 보겠습니다.
45 = 5 * 3 * 3 27 = 3 * 3 * 3
따라서 45와 27의 GCD는 9입니다.
두 숫자의 GCD를 구하는 프로그램은 다음과 같습니다.
예시
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int a = 105, b = 30;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
} 출력
GCD of 105 and 30 is 15
위의 프로그램에서 gcd()는 재귀 함수입니다. 두 개의 매개변수, 즉 및 b가 있습니다. b가 0보다 크면 a가 main() 함수로 반환됩니다. 그렇지 않으면 gcd() 함수는 b 및 a%b 값을 사용하여 자신을 재귀적으로 호출합니다. 이것은 다음 코드 스니펫에 의해 설명됩니다 -
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
} 두 숫자의 GCD를 찾는 또 다른 프로그램은 다음과 같습니다. -
예시
#include<iostream>
using namespace std;
int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a-b, b);
else return gcd(a, b-a);
}
int main() {
int a = 105, b =30;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
} 출력
GCD of 105 and 30 is 15
위의 프로그램에서 gcd()는 재귀 함수입니다. 두 개의 매개변수, 즉 및 b가 있습니다. a 또는 b가 0이면 함수는 0을 반환합니다. a 또는 b가 같으면 a를 반환합니다. 가 b보다 크면 함수는 a-b 및 b 값을 사용하여 자신을 재귀적으로 호출합니다. b가 a보다 크면 함수는 값 a와 (b - a)를 사용하여 자신을 재귀적으로 호출합니다. 다음 코드 스니펫에서 이를 확인할 수 있습니다.
int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a - b, b);
else return gcd(a, b - a);
}