최대공약수와 최소공배수

코테 단골 손님 이기도 한 최대공약수와 최소공배수 구하는 법

​

최대공약수는 유클리드 호제법을 통해서 구하는게 코딩이 훨씬 쉬운 것 같다.

​

최대공약수

​

유클리드 호제법을 통한 최대공약수 구하는 법은 간단한데

https://ko.wikipedia.org/wiki/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98

 

최대공약수 - 위키백과, 우리 모두의 백과사전

위키미디어 재단에서는 보편적 행동 강령 의 시행 지침의 초안 에 대해서 한국어 위키백과 공동체의 의견을 받고 있습니다 ( 토론 참여하기 ) 9월 20일부터 9월 30일까지 위키문헌 에서 옛 한글문헌 전자화 프로젝트 봉사자를 모집합니다. (봉사시간 부여) 74개 언어 접힘 최대공약수 위키백과, 우리 모두의 백과사전. 수론 에서, 정수 들의 공약수 (公約數, 영어 : common factor )는 동시에 그들 모두의 약수 인 정수다. 적어도 하나가 0이 아닌 정수들의 최대공약수 (最大公約數, 문화어 : 련속나눔셈; 영어 : greate...

ko.wikipedia.org

n1과 n2의 최대공약수를 유클리드 호제법을 통해 구한다고 가정

n1은 192, n2는 72일 때

​

1. 192를 72로 나눈 나머지를 구한다.

2. 72를 1에서 나온 나머지로 나누어 나온 나머지를 구한다.

3. 1에서 나온 나머지를 2에서 나온 나머지로 나눈 나머지를 구한다.

4. 위 과정을 나머지가 0이 나올때 까지 반복하고 0이 나왔을 때 나누었던 값이 최대공약수가 된다.

​

이를 코드로 보면

1.n1을 n2로 나눈 나머지를 구한다.

2.n2를 이제 다시 n1으로 보고 나머지를 n2로 본다. 를 반복하는 것이기 때문에

func getGcd(_ n1: Int, _ n2: Int) -> Int { let remainder = n1 % n2 return remainder == 0 ? n2 : getGcd(n2, remainder) }

이런 심플한 재귀함수로 구현할 수 있다.

​

​

최소공배수

최소공배수는 최대공약수를 구하면 정말 간단하게 구할 수 있는데

최소공배수는 원래 각 수의 소인수 분해를 통해 각각 지수가 가장 큰 수를 곱하면 되는데

각 수의 소인수 분해를 하는 것보다 유클리드 호제법을 통해 최대공약수를 구하는게 빠르다.

구글에 최소공배수라고 검색하면 나오는 위키 썸네일?로

n1 * n2 를 n1, n2의 최대공약수로 나누면 나온다고 되어있다.

따라서 코드로 보자면

let lcm = n1 * n2 / gcd(n1, n2)

끝.