최대공약수 & 최소공배수

- 최대공약수

private static int gcd(int p, int q){
	if(q==0) { return p; }
    return gcd(q, p%q);
}

// gcd(p,q) == gcd(q, p%q)이다.
// 리턴값이 1이라면 p와 q는 서로수이다.

 

- 최소공배수

private static int lcm(int p, int q){
	return (p*q)/gcd(p,q);
}