gcd는
예를 들어
8, 28의 최대 공약수를 구해보면
3 = 28 / 8 ...4
2 = 8 / 4 ...0
AB/GCD = GCD*a*b;
1 2 3 4 5 6 7 8 | gcd(int a, int b){ if(b == 0){ return a; } else return gcd(b, a%b); } | cs |
결국 AB/GCD는 최소공배수가 된다
'알고리즘' 카테고리의 다른 글
| 퇴각 검색(BackTracking) (0) | 2015.04.22 |
|---|---|
| 완전탐색 경우의 수를 재귀로 수행하는 방법 (0) | 2015.04.15 |
| DP(Dynamic Programming)패턴 연구 (0) | 2015.04.03 |
| 소수 판별 알고리즘 (0) | 2015.03.30 |
| 한붓그리기 조건에 대해서(오일러 서킷, 오일러 트레일) (0) | 2015.03.25 |
