유클리드 호제법 코드 예제 - 서로도 또는 최대공약수 구하기

- 유클리드 알고리즘 위키백과 :
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


- 기본 코드(Java)
public static int gcd(int a, int b) {
int tmp, n;
if (a < b) {
tmp = a;
a = b;
b = tmp;
}

// 유클리드 알고리즘 부분
// b가 0이 될때까지(a%b), 반복문을 돌게되고, b가 0인 순간의 a를 GCD로 판단하고 리턴.
while (b != 0) {
n = a % b;
a = b;
b = n;
}
return a;
}


결과가 1인경우 서로소, 1이 아닌 경우는 최대공약수가 확인됩니다.
사용하는 방법에 따라 다양하게 사용할 수 있습니다.
개인적인 활용도는 디스플레이 화면비를 구할 때 사용합니다.


예) 화면비 구하기
public class RatioCheck {

public static void main(String[] args) {
int widht = 1024;
int height = 768;
int result = gcd(widht, height);
System.out.println("Ratio > " + (widht / result) + ":" + (height / result));

widht = 1920;
height = 1080;
result = gcd(widht, height);
System.out.println("Ratio > " + (widht / result) + ":" + (height / result));

}

public static int gcd(int a, int b) {
int tmp, n;
if (a < b) {
tmp = a;
a = b;
b = tmp;
}

// 유클리드 알고리즘 부분
// b가 0이 될때까지(a%b), 반복문을 돌게되고, b가 0인 순간의 a를 GCD로 판단하고 리턴.
while (b != 0) {
n = a % b;
a = b;
b = n;
}
return a;
}

}


> 결과 :
Ratio > 4:3
Ratio > 16:9