🦖 유클리드 호제법

두 개의 수가 주어졌을때, 최대공약수(GCD)를 구하는 알고리즘

두 개의 자연수 a와 b가 주어진다.
a는 b보다 큰 자연수이며 a를 b로 나눈 나머지를 r이라고 하자.
이때 a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
따라서 r이 0일때 b가 최대공약수가 된다.

---

🌳 java로 유클리드 호제법 구현

나머지가 0이 되는 시점까지 계속해서 동일한 연산을 반복해야하기때문에 재귀형태로 구현을 해야한다.

1. 재귀함수를 이용한 최대공약수 구하기

int GCD(int a, int b){
	if(a%b==0){
    	return b;
    }
    return GCD(b,a%b);
}

2. 반복문을 이용한 최대공약수 구하기

int GCD(int a, int b){
	while(b!=0){
    	int r = a%b;
        a=b;
        b=r;
    }
    return a;
}

---

🍀 관련 문제

프로그래머스 Lv1. 최대공약수 최소공배수

---

📑 References

https://codingnojam.tistory.com/58
https://bbinya.tistory.com/45