최대공약수 구하는 법
2020. 1. 11.
이전 글에서 서로 다른 두 자연수의 공통된 약수 중에서, 가장 큰 수를 최대공약수라고 부른다 했었는데, 이번에는 최대공약수 구하는 법을 알아보자. 일단 최대공약수를 구하는 방법은 크게 2가지가 있는데, 하나는 “동시에 나눠주는 방법”이고, 또 다른 하나는 “소인수분해를 활용한 방법”이다.그럼 먼저 “동시에 나눠주는 방법”에 대해서 알아보면, 일단 최대공약수는 두 자연수의 공통된 약수이므로, 동시에 나눠줄 수가 있다. 예를 들어 84와 120의 최대공약수를 구한다고 할 때, 84와 120은 2로 동시에 나눠줄 수가 있다. 그래서 먼저 2로 나눠준다. 그럼 42와 60이 나오는데, 또 2로 나눠줄 수가 있으므로 2로 나눠준다. 이렇게 동시에 나눠줄 수 없을 때까지 계속 나눠주면, 최대공약수를 구할 수 있다...