유클리드 호제법

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘이다.

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

24와 18의 최대 공약수를 구해보자

큰수를 작은수로 나누어 나머지를 구한다.

24=18*1+6

 

45와 38의 최대 공약수는 38과 7의 최대 공약수와 같다. 이성질을 재귀적으로 이용한다.

위 과정을 반복하여 나머지가 0이 될때 나누는 수가 최대공약수이다.

 

18=6*3

 

따라서 6이 최대공약수임을 알 수 있다.

 

코드

import java.util.Scanner;




public class Hello {
	static int gcd(int p,int q) {
		if (q==0)return p;
		return gcd(q,p%q);
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int a= scanner.nextInt();
		int b= scanner.nextInt();
		int min=Math.min(a, b);
		int max=Math.max(a, b);
		int ggcd= gcd(max,min);
		System.out.println(ggcd);
		
	}
}

 

최소공배수

최소공배수는 두 수를 곱하고 최대공약수로 나누어 주면 된다.