프로그래밍/알고리즘
알고리즘 - 최대공약수(GCD) & 최소공배수(LCM) (유클리드 호제)
맹이맹이
2020. 6. 15. 01:18
반응형
유클리드 호제란?
- 2개의 자연수의 최대 공약수를 구하는 알고리즘
1) 최대 공약수 구하기
-> 우선 A와 B라는 변수에 값을 받는다!
-> gcd라는 메서드의 인자 값으로 A, B를 넘겨준다.
-> B의 값이 0이 될 때까지 반복문을 통해 수행한다
-> mod라는 임시 변수를 생성해서 A / B를 한 나머지 값을 저장하고
-> A에 B의 값을, B에 mod 값을 저장시킨다
-> b가 0이 되면 result 변수에 a 값을 넣고 반환한다!
사진을 보면 이해가 쉬울 것이다. 16, 24를 받아서 반복문을 통해 최대공약수를 찾아낸다
2) 최소 공배수 구하기
앞서 최대공약수를 구했다면 최소공배수는 쉽게 구할 수 있다!
lcm이라는 최소 공배수를 구하는 메서드를 생성하고 지역변수 a, b를 통해 값을 비교 값을 받는다.
그리고 a, b를 곱하고 최대공약수를 나눠주면 최소 공배수가 나오게 된다!
혹시나 궁금한 점은 댓글로 남겨주세요!
반응형