최대공약수

최대공약수와 최소공배수의 관계

일단 두 자연수 A와 B 그리고 최대공약수 G와 최소공배수 L을 그림으로 표현하면 아래와 같은데, 해당 그림을 보면 몇가지 규칙을 알 수 있다. 먼저 최소공배수 L = G * a * b  그리고 자연수 A를 G로 나누면 a가 나오므로 A = G * a이고, 자연수 B를 G로 나누면 b가 나오므로 B = G * b라는 것도 알 수 있다. 그럼 여기서 두 자연수인 A와 B를 서로 곱해보면, A * b = G * a * G * b가 된다. 그리고 A * B = G * a * G * b의 순서를 바꿔보면, A * B = G * G * a * b라고 나타낼 수 있는데, 위에서 L = G * a * b라고 했으니, G * a * b에는 L을 대입할 수가 있다. 그래서 최종적으로 A * B = G * L이 되는 것을..

최대공약수와 최소공배수란

서로 다른 두 자연수라도 약수를 구해보면 똑같이 공통된 약수가 있다. 예를 들어 자연수 12와 18의 약수를 구해보면 아래와 같은데, 이 중에서 1, 2, 3, 6은 똑같이 공통된 약수다, 그리고 이렇게 서로 다른 두 자연수의 공통된 약수를 보통 공약수라고 한다. 또 공약수 중에서 가장 큰 수를 최대공약수라고 하는데, 자연수 12와 18의 최대공약수는 6이다. 최대공약수를 알면 공약수 구하기가 쉬워진다 왜냐면 최대공약수의 약수가 바로 공약수이기 때문이다, 그래서 일일이 약수를 구해서 공약수를 찾지 않아도, 최대공약수만 알면 쉽게 공약수를 구할 수 있다. 물론 12와 18의 경우에는 숫자가 작아서, 공약수를 일일이 구해도 상관없지만, 숫자가 클 경우에는 공약수 구하기가 번거롭다. 예를 들어 자연수 1800..

유클리드 호제법 - 최대공약수(GCD) 구하기

유클리드 알고리즘(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 비교대상의 두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다."라는 원리를 활용한 알고리즘이다. ex) GCD(24,16) -> GCD(16,8) -> GCD(8,0) : 최대공약수 = 8 구현 재귀 함수 활용 int GCD(int a, int b) { if(b==0)return a; else return GCD(b,a%b); } 반복문 활용 int GCD(int a,int b){ while(1){ int r = a%b; if(r==0) return b; a = b; b = r; }..