최대 공약수(GCD), 최소 공배수(LCM) 구하기, 유클리드 호제법 - JAVA
최대 공약수와 최대 공배수의 개념 1) 공약수 두 정수의 공통 약수를 공약수라고 한다. 두 정수 a, b에 대하여 e가 a의 약수이면서 b의 약수일 때 e를 a, b의 공약수라고 한다. 2) 최대공약수 두 정수의 공약수 중 가장 큰 것을 최대공약수라고 한다. 또한 최대공약수는 다음의 성질을 만족한다. a, b의 최대공약수가 g이다. ⇔ a = ga′, b = gb′이면 a′, b′는 서로소이다. 3) 공배수 두 정수의 공통 배수를 공배수라고 한다. 두 정수 a, b에 대하여 c가 a의 배수이면서 b의 배수일 때 c를 a, b의 공배수라고 한다. 4) 최소공배수 양의 공배수 중 가장 작은 것을 최소공배수라고 한다. [네이버 지식백과] 최대공약수와 최소공배수 (통합논술 개념어 사전, 2007. 12. 15...
2022. 12. 16.
