매일매일 IT
유클리드 호제법(Euclidean algorithm) 본문
ユークリッドアルゴリズム
- 유클리드 호제법(- 互除法, Euclidean algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나.
- 호제법 : 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘.
- 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 유클리드의 《원론》 제7권, 명제 1부터 3까지에 해당.
- n이 0이라면, m을 출력하고 알고리즘을 종료한다.
- m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
- 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.
- 위 과정은 “n, m에 대해서 나머지 연산을 실시할 수 있다”라는 조건에만 의존하므로, 정수환뿐 아니라, 임의의 유클리드 정역에 대해도 똑같은 과정을 거치면 공약인자가 구해진다.
import java.util.Scanner;
public class GcdLcm {
public static int GCD(int a, int b){ //GCD method signature. Takes two values and returns the GCD.
int temp;
if(a==b){ //Euclidean algorithm implementation. Recursion stopping case.
return(a);
}
if(a<b){ //Recursion. if a<b; switch to make a>b
temp=a;
a=b;
b=temp;
}
return(GCD(a-b,b)); //euclidean algorithm: GCD(a,b)=GCD(a-b,b)
}
public static int LCM(int a, int b){ //LCM method signature. Takes two values and returns LCM.
return(a*b/(GCD(a,b))); //by definition, a*b=GCD(a,b)*LCM(a,b)
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num1, num2;
System.out.println("*** 두 수의 최대공약수와 최소공배수 ***");
System.out.print("첫 번째 수 입력: ");
num1 = sc.nextInt();
System.out.print("두 번째 수 입력: ");
num2 = sc.nextInt();
System.out.println("최대공약수: " + GCD(num1, num2) + "\n최소공배수: " + LCM(num1, num2));
}
}
// JAVA SOURCE CODE_WIKI
public static int gcd(int p, int q)
{
if (q == 0) return p;
return gcd(q, p%q);
}