GCD와 LCM의 관계
A와 B의 최대공약수를 G
, 최소공배수를 'L'이라 할 때, 다음 식이 성립한다.
(A*B)/G = L
WHY?
왜 Lcm = G*a*b 예요?
최소공배수는 두 수 A,B의 공통된 배수 중 최소값임.
최소가 되려면, 불필요한 계산이 없어야함. 서로가 필요로 하는 최소의 값인 서로소만 곱하여 표현하면 그것이 최소공배수다.
'알고리즘 > 알고리즘-이론' 카테고리의 다른 글
유클리드 호제법 (정의, 원리, 증명) (0) | 2024.09.24 |
---|---|
이분 탐색 & Upper Bound, Lower Bound 개념 정리 (0) | 2024.07.24 |
[자료구조] 그래프를 자료구조로 나타내보자! (0) | 2024.07.12 |
DFS와 BFS (0) | 2024.07.11 |
소수 판별법 (낱개의 숫자에 대하여, 에라토스테네스의 체) Java (0) | 2024.07.11 |