• 두 정수의 최대공약수 문제

▸problem #1: 최대공약수

최대공약수의 활용

최대공약수는 비단 일상생활에서만 사용되는 것은 아니다. 다양한 과학적인 상황에서도 폭넓게 사용되고 있다. 예를 들어, 1923년 기본 전하와 광전효과에 대한 연구로 노벨 물리학상을 받은 로버트 밀리컨(Robert Millikan, 1868~1953)은 가장 작은 전하량인 기본 전하량 e의 크기를 구하기 위해 실시한 기름방울시험에서 최대공약수를 활용하였다.

밀리컨은 이 실험에서 중력에 의해 내려가는 기름방울의 힘과 두 금속 전극 사이에 정지되어 있는 작은 기름방울에 작용하는 힘 사이의 균형 상태를 측정하였다. 이러한 수백 번의 실험 끝에 기름방울에 있는 전하량의 크기들을 구하였다. 그런데, 모든 전하량의 크기는 전자가 가지는 기본 전하량(e)의 정수배가 되어야 한다는 사실로부터, 기본 전하량 e를 기름방울실험에서 얻은 전하량들의 최대공약수를 통해 얻는데 성공하였다.

▸problem #2:

최대공약수와 최소공배수의 활용

돈을 아끼고 싶다면 최대공약수를, 미래를 예측하고 싶다면 최소공배수를 활용해 보는 것은 어떨까요?
분배에 있어 효율성과 공평성은 매우 중요합니다. 자원의 낭비를 줄이려면 효율적이어야 하고, 서로 다툼이 없으려면 공평해야 하지요.
이 문제에 대한 해답을 최대공약수와 최소공배수가 제시합니다.

▸Algorithm: 이 문제를 컴퓨터로 풀 수 있을까? - 기계적 계산

두 정수의 최대공약수

http://en.wikipedia.org/wiki/Greatest_common_divisor

http://en.wikipedia.org/wiki/Euclidean_algorithm

1) Algorithm #1:

GCD(a, a)=a

GCD(a, b)=GCD(a-b, b)	, if a>b

GCD(a, b)=GCD(a, b-a)	, if b>a

(from 서울, 초등)

즉, 유클리드 호제법은 “두 정수 m,n(m>n)이 있을 때, m과 n의 최대공약수는 m-n과 n의 최대공약수와 같다”라는 명제를 기초로 한다.

이를 알고리즘으로 정리하면

가) m과 n이 같지 않으면 다음을 반복한다.

나) m>n이면 m=m-n, 그렇지 않으면 n=n-m

다) m과 n이 같다면 m(또는 n)이 구하고자 하는 최대공약수이다.

예) m=24, n=18

m         n

24         18

24-18=6         18

6       18-6=12

6        12-6=6

GCD = 6

The algorithm proceeds by successive subtractions in two loops:

IF the test B ≥ A yields "yes" (or true) (more accurately the number b in location B is greater than or equal to the number a in location A)

THEN the algorithm specifies B ← B − A (meaning the number b − a replaces the old b).

Similarly IF A > B THEN A ← A − B.

The process terminates when (the contents of) B is 0, yielding the g.c.d. in A.

2) Algorithm #2:

GCD(a, 0)=a

GCD(a, b)=GCD(b, a mod b)	, where a mod b=a를 b로 나눈 나머지값

e.g.,	GCD(34398, 2132)=GCD(2132, 286)

GCD(2132, 286)=GCD(286, 130)

GCD(286, 130)=GCD(130, 26)

GCD(130, 26)=GCD(26, 0)

GCD=26

(from 서울, 중등 기초)

유클리드 알고리즘은 최대공약수에 관한 아래 결과와 나눗셈 알고리즘을 바탕으로 한다.

[보조정리]

a, b, q, r이 정수일 때 a=bq+r이라 하자. 그러면 gcd(a,b) = gcd(b,r)

유클리드 알고리즘은 최대공약수(gcd)를 찾는데 아주 효율적인 방법이다. 유클리드 알고리즘을 설명하기 전에, gcd(91,287)을 찾는데 이 알고리즘이 어떻게 사용되는지를 보인다.

먼저, 두 정수 중 큰 수인 287을 작은 수 91로 나누어 287=91․ 3+14를 얻는다. 91과 287의 어떤 약수이든지 287-91․ 3=14의 약수임에 틀림없다. 또, 91과 14의 어떤 약수이든지 287=91․ 3+14의 약수임에 틀림없다. 그래서 91과 287의 최대공약수는 91과 14의 최대공약수다. 이것은 gcd(91,287)을 찾는 문제는 gcd(91,14)를 찾는 문제로 축소됨을 의미한다. 다음으로 91을 14로 나누어 91=14 ․ 6+7을 얻는다. 91과 14의 공약수는 역시 91-14 ․ 6=7을 나누고 14와 7의 공약수는 91을 나눈다. 그래서 gcd(91,14)= gcd(14,7)이다.

계속하여 14를 7로 나누어 14=7 ․ 2를 얻는다. 7이 14를 나누므로 gcd(14,7)=7이다. 더욱이, gcd(287,91)=gcd(91,14)=gcd(14,7)=7이므로 원래의 문제가 풀린다.

유클리드 알고리즘의 작동은 최대공약수를 구할 때, 두 양의 정수의 최대공약수를 찾는 문제를 보다 작은 정수들의 문제로 축소하기 위해 나눗셈을 어느 한쪽이 0이 될 때까지 연속적으로 행한다.

▸Program #1 (C program)

// file I/O 사용...

#include<stdio.h>

void main()

{

FILE *inf, *outf;

int m,n;

inf=fopen("d:/temp/input.txt","r");

outf=fopen("d:/temp/output.txt","w");

fscanf(inf,"%d%d",&m,&n);

while(m!=n)

{

if(m>n)

m=m-n;

else

n=n-m;

}

fprintf(outf,"%d",m);

fclose(inf);

fclose(outf);

}

▸Program #2 (Android App)

https://play.google.com/store/apps/details?id=com.scapelitte.lcmgcdfinder&hl=ko

▸Program #3 (HTML5 Web App)

http://comedudb6.knue.ac.kr/tykim/Myhome/CAInote/GCD/gcd.html