유클리드 호제법과 확장 유클리드 알고리즘

유클리드 호제법 사용 이유 유클리드 호제법은 최대 공약수 (gcd) 를 구하는 알고리즘 중 하나이다. 대부분 최대 공약수를 구하기 위해 인수분해를 이용했을테지만, 말도 안 되게 큰 수의 최대공약수는 인수분해로 풀기 어렵기 때문에, 유클리드 호제법을 사용한다. 예를들어, 12345 와 123의 최대 공약수를 구해야 할 때는 인수분해보다 유클리드 호제법을 사용할 때 더 빠르게 구할 수 있다. 유클리드 호제법은 큰 수들의 최대공약수를 쉽게 구하기 위한 알고리즘이다. 유클리드 호제법 과정 12345 와 123의 최대 공약수를 유클리드 호제법으로 구하면서 방법을 보여주겠다. 이런 식으로, 처음에 두 수 12345 , 123 이 주어졌다면 12345를 123을 이용해서 나타내준다. 12345 = 123 * 100 ..

2024.03.23