[제 4강] 최대공약수.function

최대공약수 (유클리드 알고리즘을 이용)

gcd(a,b)로 표현 하기도 하는 이번 글에선 최대공약수를 다뤄보려고 한다.

 

우리가 보통 최대공약수를 구하는 방법음 다음과 같다.

2 │ 48  18
3 │ 24   9
   └────
         8     3
이렇게 구한 뒤에 세로로 곱한다면 최대공약수가 나오는 방식으로 여태까지 구해 왔다.

하지만 컴퓨터는 이러한 방법으로는 최대공약수를 구하지 못한다.
또한 각 수를 모두 소수로 분해해야 하기에 매우 비효율적이다.

지금부터 컴퓨터가 해결할 수 있도록 위에서 구한 식을 함수 gcd(a,b)를 이용해 풀어보자.

======================================================================

그전에 먼저 mod(모듈러)에 대해 알아야 한다.
mod 계산은 C언어의 %연산자와 같은 역할은 한다. 즉, 나머지를 구하는 연산자라는 것이다. 

예를 들어,

105 mod 10 = 5 이다.

또한 mod연산자는 양쪽에 쓰지 않고 한쪽으로 몰 수 있는데,
105 = 15 (mod 10) 이렇게쓰여 있다면,
105 mod 10 = 15 mod 10
5 = 5가 된다.

======================================================================

그럼 이제 다시 최대공약수로 돌아가서 함수 gcd(a,b)에 대해 알아보자.

함수 gcd(a,b)의 작동 방식은 gcd(a,b) = gcd(b,a mod b)로 매우 단순하다.
예를 들어, a=48, b=18 이라면,

gcd(48,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) 이 된다.
그리고 b=0이므로 gcd(48,18) = gcd(6,0)= 6 이다.
즉, b자리0이되최대공약수는 a인 것이다.

 

자 이제 알고리즘을 만들어 보자 (유클리드 알고리즘)

1. gcd(a,b)에서 b값이 0이 아니라면, a mod b 연산을 실행
2. a 자리에 b를 넣고 a mod b의 결과를 b의 자리에 넣는다.
3. 1,2를 반복한다. 만약 b=0이라면 a값이 최대공약수이다.

알고리즘은 mod 만 안다면 매우 간단하다.
이제 알고리즘을 C로 코딩해보자.

#include <stdio.h>
#include <stdlib.h>
#define INT unsigned int 

INT gcd(INT a, INT b) {
	if (0 == b) return a;
	return gcd(b, a % b);
}

끝이다. 정말 이게 끝이다.
솔직히 이런 방법은 생각치도 못했었다. 하지만 누가 2줄로 완성했다는 소리를 듣고 어떻게 짜야 2줄 이내로 짤 수 있을까 고민 하던 중

“반환 값을 함수로 주면 되겠다.” 라는 생각에 실제로 해보니 결과는 성공적이였다. 여기서 한 수 알아갔다.

이로써 최대공약수와 소수를 찾을 수 있게 되었다.

이제 N=p×q, (N) = (p-1)(q-1)와 유클리드 호제법만 만들면 RSA를 만들기 위한 기본적인 함수 준비는 모두 끝나게 된다.

 

 

 

글의 문제가 있다면 댓글을 달아 주세요.

This site uses Akismet to reduce spam. Learn how your comment data is processed.