최대 공약수, 최소 공배수 알고리즘
기존의 그냥 하나씩 대입해서 최대 공약수는 찾는 알고리즘은 의 시간복잡도를 가진다.
유클리드 호제법을 사용하면 의 시간복잡도를 가진다.
이라고 가정하자.
•
204 mod 48 = 12
•
48 mod 12 = 0
12가 204와 48의 최대 공약수이다.
왜그럴까?
증명
A와 B의 최대공약수는 B와 r의 최대 공약수와 같다.
A와 B는 최대공약수에 어떤 수를 곱한 수이다.
A와 B의 최대공약수에 곱해져 있는 수들은 서로소여야 한다. (아니면은 최대공약수가 아님)
서로소 : 두 수를 같이 나누어 떨어지는 수가 1밖에 없는 경우
G : 최대 공약수
A를 B로 나누었을때 몫이 q 나머지가 r이라고 할 때
정리하면
b와 (a - qb)가 서로소이면 말이 된다.
증명하기 위해 귀류법을 사용한다.
증명이 틀렸다고 가정했을때 전제조건에 모순이 있는지 확인하는 증명방법이다.
공통된 약수가 있다고 가정을 해보자.
정리하면
a와 b는 n이라는 공통된 약수가 존재한다. 그런데 전제는 a와 b는 서로소이다.
공통된 약수가 있다는 가정을 했을때 전제에 모순이 발생한다. → 따라서 a와 b는 서로소이다.
알고리즘
최대 공약수 (유클리드 호제법)
// greatest common divisor
int getGCD(int a, int b)
{
int r;
while (b != 0)
{
r = a % b;
a = b;
b = r;
}
return b;
}
C++
복사
최소 공배수
두 수를 곱한것을 최대 공약수로 나누면 최소 공배수가 나온다.
// lowest common multiple
int getLCM(int a, int b, int gcd)
{
return (a * b / gcd);
}
C++
복사
