반응형
유클리드호제법을 사용하여 최대공약수를 찾는 알고리즘은 다음과 같다.
pubic int getCommon(int a, intb){
int n=0;
while(b!=0){
n = a%b;
a = b;
b = n;
}
return a;
}
이 알고리즘은 a>b일 때 둘을 나누면서 최대 공약수를 찾는 방식이다.
이렇게 직접 알고리즘을 구현해도 되고 BigInteger의 메소드를 사용하는 방법도 있으며 그 방식은 아래와 같다.
public int getCommon(int a, int b){
BigInteger num1 = BigInteger.valueOf(a);
BigInteger num2 = BigInteger.valueOf(b);
BigInteger gcd = num1.gcd(num2);
return gcd.intValue();
}
반응형
'알고리즘' 카테고리의 다른 글
최소신장트리 (0) | 2020.12.06 |
---|---|
String, StringBuilder, StringBuffer (0) | 2020.11.23 |
Hash Table (0) | 2020.11.15 |
스택과 큐 (0) | 2020.09.06 |
console에서 값 읽을 때 (0) | 2020.09.06 |