자료구조, 알고리즘/기본다지기
[수학] 최대공약수(GCD)와 최소공배수(LCM) 구하기
민쓰
2018. 8. 10. 19:44
최대공약수(GCD)
- 두 수의 공통된 약수 중에서 가장 큰 정수
- 최대공약수가 1인 두 수는 서로소
코드
private int gcd(int a, int b) { if(b==0){ return a; } else{ return gcd(b, a%b); } }
- 유클리드 호제법
- a를 b로 나눈 나머지 r
- GCD(a,b) = GCD(b,r)
- r = 0 일 때 b가 최대공약수
재귀함수 사용하여 구현한 코드
private int gcd(int a, int b) { if(b==0){ return a; } else{ return gcd(b, a%b); } }
재귀함수 사용하지 않고 구현한 코드
private int gcd(int a, int b) { while(b !=0){ int r = a%b; a = b; b = r; } return a; }
최소공배수(LCM)
- 두 수의 공통된 배수 중에서 가장 작은 정수
- 최대공배수는 GCD를 응용해서 구할 수 있음
- 최소공배수 l = g * (a/g) * (b/g)
코드
private int lcm(int a, int b) { int g = gcd(a,b); return g*(a/g)*(b/g); }