최소공배수

[알고리즘] 최대 공약수, 최소공배수

최대 공약수를 구하는 알고리즘 중 가장 유명한 유클리드 호제법에 대해 알아보자. 유클리드 호제법 a를 b로 나눈 나머지를 r이라고 할 때, GCD(a, b) = GCD(b, r)이다. r이 0일 때의 b가 최대 공약수이다. 위의 정의를 GCD(24, 16)을 통해 알아보자. 1. 24(a)를 16(b)로 나눈다. 24 % 16 = 8(r) 2. 16(b)를 8(r)로 나눈다. 3. 8(b)와 0(r)을 계산해야 하는데 r = 0이므로 이 때의 b값인 8인 최대 공약수가 된다. int gcd(int a, int b) { while ( b != 0) { int r = a % b; a = b; b = r; } return a; } 최소공배수 최소공배수는 LCM이라고 하며 GCD를 응용해서 구할 수 있다. 최소..