알고리즘 - 최대공약수(GCD) & 최소공배수(LCM) (유클리드 호제)

유클리드 호제란?

​

- 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를 곱하고 최대공약수를 나눠주면 최소 공배수가 나오게 된다!

​

 

​

​

 

​

​

혹시나 궁금한 점은 댓글로 남겨주세요!

​