최대공약수 최소공배수 구하는 가장 쉬운 법 (ft. 유클리드호제법)
최대공약수(GCD Greatest Common Divisior ) 두 자연수의 공통 약수 중 가장 큰 자연수 ex. 32의 약수 1, 2, 4, 8, 26, 32 24의 약수 1, 2, 3, 4, 6, 8, 12, 24 ∴ GCD(32, 24) = 8 최소공배수(LCM Least Common Multiplier) 두 자연수의 공통 배수 중 가장 작은 자연수 ex. 32의 공배수 32, 64, 96, ... 24의 공배수 24, 48, 72, 96, ... ∴ LCM(32, 24) = 96 또한, 최소공배수는 32*24/GCD(32,24)로도 구할 수 있다. 유클리드 호제법(Euclidean algorithm) 위키에 따르면, 유클리드 알고리즘은 두 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나라..
2021. 9. 15.
