본문 바로가기

# Foundation/기초수학

최대 공약수와 최소 공배수의 관계

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
    https://github.com/AeroCodeX/

두 정수의 최대공약수와 최소공배수의 관계

두 정수 a, b에 대하여, 이것의 최대공약수와 최소공배수를 각각 hcf, lcm이라 하면 아래와 같은 등식이 성립된다.

HCF (Highest Common Factor)   : 최대 공약수
GCD (Greatest Common Divisor) : 최대 공약수
LCM (Lowest Common Multiple) : 최소 공배수


증명은 다음과 같다.



숫자가 여러개일 때, 최대공약수와 최소공배수의 관계

숫자가 3개 또는 4개 이상일 때도 비슷하게 흘러간다.

'# Foundation > 기초수학' 카테고리의 다른 글

피보나치 수열 알고리즘  (0) 2018.11.03
소수 알고리즘  (0) 2018.10.26
최소 공배수 알고리즘  (0) 2018.10.23
최대 공약수 알고리즘  (0) 2018.10.22
약수 알고리즘  (0) 2018.10.21