※이건 수학과 관련된 프로그래밍입니다. 유클리드 호제법이 이해가 안 되신다면 넘어가셔도 좋습니다※
유클리드 호제법, 들어보셨나요? 유클리드 호제법은 두 수의 최대공약수를 소인수분해 없이 구할 수 있는 방법입니다. 이해가 안 되실 수 있어요;;; 유클리드 호제법은 다음과 같이 정의할 수 있습니다.
- 두 수 중에서 큰 수를 a, 작은 수를 b라고 하고 a를 b로 나눈다.
- a가 b로 나누어떨어지면 두 수의 최대공약수는 b이다.
- a가 b로 나누어떨어지지 않으면 a를 b로 나눈 나머지와 b에 대하여 1번부터 다시 반복한다.
이렇게 계속 반복하면 최대공약수가 나오겠죠? 최대공약수가 나오면 최소공배수는 두 수의 곱을 최대공약수로 나누어 구할 수 있습니다. 이 유클리드 호제법을 한 번 반복문으로 짜볼 겁니다. 한 번 잠시 종이에 써보세요. 어려울 거에요. 프로그램의 결과와 소스 코드는 이렇게 됩니다.
입력: 4, 6 => 두 수를 입력합니다.
출력: 2 12 => 최대공약수와 최소공배수를 출력합니다. 만약 두 수 중 하나가 0이라면 프로그램을 종료합니다. 종료되기 전까지는 프로그램이 계속 반복됩니다.
...(a, b에 0이 입력될 때까지 반복)...
int a, b, c, d, e, gcd, lcm;
while (1)
{
scanf("%d %d", &a, &b);
if(a == 0 || b == 0)
{
printf("END");
return 0;
}
if(a > b)
{
c = a;
d = b;
}
else
{
c = b;
d = a;
}
while (1)
{
e = c % d;
if(e == 0)
{
gcd = d;
lcm = a * b / gcd;
printf("%d %d\n", gcd, lcm);
break;
}
c = d;
d = e;
}
}
return 0;
와 어렵죠? 해석 들어갈게요
a, b를 두 수로 둡니다. c,d는 일단 두고 e를 a와 b를 나눌 나머지 변수로 둡니다. gcd와 lcm은 최대공약수와 최소공배수를 담는 변수입니다.
일단 a, b를 입력 받고, a, b 중 하나라도 0인지 확인합니다. 만약 참이라면 return 0;을 해서 프로그램을 종료하고, 아니면 다음으로 넘어갑니다(여기에는 굳이 else가 필요 없는게 if문이 참이라면 그냥 프로그램이 종료되어서 다음 코드로 넘어간다는 것은 if문이 거짓이라는 것이나 다름 없습니다)
이제 a, b를 큰 수, 작은 수로 정렬을 해야 합니다. 여기에서 c, d가 등장합니다. 일단 a가 큰지 b가 큰지 살펴보아야 합니다. 조건문으로 c에는 큰 수, d에는 작은 수를 놓습니다.
여기에서 또 무한 루프를 또 돌리는데요, 여기에서는 유클리드 호제법의 반복을 씁니다. c, d가 나누어 떨어질 때까지 나머지를 e로 저장해 계속 무한 루프를 돌리는 것입니다. 이렇게 하다 보면 결국 c, d가 나누어 떨어질 때가 있을 것입니다. 그 때 gcd에다가 d를 저장하고, lcm은 a * b / gcd를 하면 나오겠죠? 이 두 변수를 출력하고 반복문을 탈출합니다. 그러면 반복문이 바깥에 있는 반복문으로 돌아가서 처음부터 다시 시작하겠죠? a, b가 0이 되지만 않는다면요^^
와우 엄청 기네요. 이 유클리드 호제법은 재귀함수 때 다시 나올 거니까 그 때 다시 기다려주세요! 그때는 훨씬 더 쉬워질 거에요.
