문제
C 프로그래밍 언어를 사용하여 임의의 두 숫자에 대한 최대공약수(GCD)를 구해야 합니다.
해결 방법
사용자가 콘솔에서 두 개의 숫자를 입력하도록 한 뒤, 입력받은 두 숫자에 대한 최대공약수를 계산합니다.
두 숫자의 GCD(최대공약수)란 두 숫자를 모두 나머지 없이 정확하게 나눌 수 있는 가장 큰 수를 의미합니다.
두 숫자의 GCD를 구하기 위해 사용하는 논리는 다음과 같습니다 −
while(b!=0) // a/b 연산에서 b는 0이 아니어야 하므로 b=0 조건 검사
{
rem=a % b;
a=b;
b=rem;
}
a 값 출력유클리드 호제법 이해하기
위 코드는 유클리드 호제법(Euclidean Algorithm)을 기반으로 동작합니다. 이 알고리즘은 두 수 중 큰 수를 작은 수로 나눈 나머지를 구하고, 다시 작은 수를 그 나머지로 나누는 과정을 나머지가 0이 될 때까지 반복합니다. 나머지가 0이 되는 시점의 값이 바로 두 수의 최대공약수입니다.
프로그램 1: while 루프 사용
#include<stdio.h>
int main(){
int a,b,rem;
printf("enter any two numbers:");
scanf("%d%d",&a,&b);
while(b!=0){ // a/b 연산에서 b는 0이 아니어야 하므로 b=0 조건 검사
rem=a % b;
a=b;
b=rem;
}
printf("GCD of two numbers is:%d\n",a);
return 0;
}출력 결과
enter any two numbers:8 12 GCD of two numbers is:4 검증: 8 = 2 * 2 * 2 12 = 2 * 2 * 3 두 숫자의 최대공약수 : 2 * 2 = 4
프로그램 2: for 루프 사용
이번 예제에서는 for 루프를 사용하여 두 숫자의 GCD를 구해 보겠습니다−
#include <stdio.h>
int main(){
int num1, num2, i, GCD;
printf("enter two numbers: ");
scanf("%d %d", &num1, &num2);
for(i=1; i <= num1 && i <= num2; ++i){
if(num1%i==0 && num2%i==0)
GCD = i;
}
printf("GCD of two numbers is:%d", GCD);
return 0;
}이 방식은 1부터 두 숫자 중 작은 값까지 차례대로 반복하면서, 두 숫자 모두를 나눌 수 있는 가장 큰 값을 찾는 완전 탐색(Brute Force) 방식입니다. while 루프를 사용한 유클리드 호제법보다 계산 속도는 느리지만, 로직이 직관적이라 초보자가 이해하기 쉽다는 장점이 있습니다.
출력 결과
enter two numbers: 24 48 GCD of two numbers is:24