최대공약수, 최소공배수

구현

//최대공약수, 최소공배수 구하기 : 유클리드 호제법
long gcd=0;
long min = a < b ? a : b; //작은 수 기준

for(int i=1; i <= min; i ++) {
    if(a % i ==0 && b % i ==0) { //둘다 나누어 떨어져야함
        gcd = i;
    }
}

System.out.println( "최대공약수 :" + gcd);
System.out.println( "최소공배수 :" + (a * b) / gcd);

 

BigInteger 내장함수 사용

import java.math.BigInteger;

//최대공약수
long gcd = BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue();

//최소공배수
long lcm = (a * b) / gcd