N보다 작은 특정 수의 배수를 찾아보자[최대 공약수, 최소 공배수, 교집합, Ugly Number III]
## 접근방법 간단히 생각해보자, N보다 작은 2의 배수의 개수는 몇 개일까? 정답은, N / 2개이다. N / 2개가 된다는 사실은 자명하므로 증명은 생략하겠다. A와 B가 있을 때, 두 수의 최대 공약수는 얼마일까? GCD(A, B) = GCD(B, A % B)이다. 증명은 아래와 같다. GCD(A, B) = G일 때, GCD(B, A % B)의 최대공약수도 G일까? A = G * a B = G * b A = B * q + r A % B = r = A - B * q B = G * b r = A - B * q = G * a - G * b * q= G(a - bq) 으로 증명될 수 있다. 이제 최소 공배수에 대해서 알아보자, 최소 공배수는 두 수의 곱에다가 최대 공약수를 나눠주면 된다. LCM(A, B)..
