최대공약수, 최소공배수, 유클리드 호제법

두 수 A, B를 120, 36이라고 했을 때 각각 소인수 분해 하면

A(120): 2*2*2*3*5
B(36): 2*2*3*3

• 최대공약수(Greatest Common Division)
  공통된 소인수인 (2, 2, 3)
• 최소공배수(Least Common Multiple)
  두 수의 소인수 합집합인 (2*2*2*3*3*5)

유클리드 호제법(GCD 찾기)

A를 B로 나눈 몫을 Q라 하고, 나머지를 R이라고 했을 때, gcd(A, B) = gcd(B, R) 이다.

호제법의 정의에 따라, 서로 나눠주다가 한 수가 0이 됐을 때 다른 수를 return 하면 된다.

int gcd(int a, int b){
	int bigger=Math.max(a, b);
    int smaller=Math.min(a, b);
  
    while(smaller!=0){
    	int temp=smaller;
        smaller=bigger%smaller;
        bigger=smaller;
    }

    return bigger;
}

최대공약수(LCM 찾기)

위의 벤 다이어그램에서 소인수의 합집합을 구하면 된다.
A(120)과 B(36)을 곱하면 교집합(GCD)은 두 번 곱해지므로, 합집합-교집합을 하면 된다.

A x B / gcd(A, B)

int lcm(int a, int b){
	return a*b/gcd(a, b);
}