최대공약수, 최소공배수


유클리드 호제법을 사용하여 최대공약수를 구함

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




public class Main {


public static void main(String[] args) {


int g = gcd(78696, 19332); //유클리드 호제법 사용

System.out.println(g);//36


int l = lcm(78696, 19332);

System.out.println(l);//42259752

}


static int gcd(int p, int q) {

if(q == 0) return p;

return gcd(q, p%q);

}

static int lcm(int A, int B){

int g = gcd(A,B);

int a = A/g;

int b = B/g;

return g*a*b; //최소공배수

}

}