알고리즘 - 최대공약수 구하기 (유클리드 호제법) - C++

---

개요

 

이번에는 유클리드 호제법을 이용하여

최대공약수를 구해보도록 하겠습니다.

 

---

설명

 

유클리드 호제법

X를 Y로 나눈 나머지 값을 R이라고 했을 때,

X와 Y의 최대공약수는 Y와 R의 최대공약수와 같습니다.

 

Ex)

85 % 51 = 34

51 % 34 = 17

34 % 17 = 0

---

풀이

 

#include <iostream>

using namespace std;
int gcd(int x, int y) {

	int z=1;
	while (z!=0) {

		z = x % y;
		x = y;
		y = z;
		
	}
	return x;
	

}

int main() {
	int x,y;
	cin >> x >> y;
	
	cout << x << " 와 " << y << " 의 최대 공약수 = " << gcd(x,y);


	return 0;
}

 

---