반응형

목록유클리드 알고리즘 (1)

기억 휘발 방지소

유클리드 알고리즘 (Euclidean Algorithm)

📌 유클리드 호제법 일반적인 최대공약수를 구하는 방법은 두 수의 공통 약수를 모두 구해 곱하는 방법입니다. 100과 40의 최대공약수를 다음과 같이 구할 수 있습니다. 100 = 2^2 * 5^2 40 = 2^3 * 5 ------------------------ 최대공약수 = 2^2 * 5 = 20 유클리드 호제법은 일반적인 방법과는 좀 다른 방법으로 두 수의 최대공약수를 구합니다. 유클리드 호제법은 다음과 같이 구할 수 있습니다. 먼저 큰 수를 작은 수로 나눈 나머지를 구합니다. 100 % 40 = 20 (%는 나머지를 구하는 연산자) 그 다음 나눴던 작은 수를 나머지로 다시 나누고 나머지를 구합니다. 나머지가 0이 될 때까지 이 과정을 반복합니다. 나머지가 0이 되었을 때, 마지막으로 나눈 수가 최..
Algorithm 2022. 9. 7. 17:56
이전 Prev 1 Next 다음
반응형