728x90
반응형
GCD
-
TIL : Javascript로 최대공약수(Greatest Common Divisor, GCD) 구하는 함수 만들기캡틴 코딩일기/javascript 2020. 3. 21. 23:35
TIL : Javascript로 최대공약수(Greatest Common Divisor, GCD) 구하는 함수 만들기 최대공약수? 언제 배웠는지도 기억이 없는 산수 개념을 가지고 함수를 만들게 되었다. '두 가지 숫자가 주어지면, 두 숫자의 최대공약수를 반환하는 기능' 을 구현하는 것이 오늘의 목표. 먼저, 최대공약수의 정의와 알고리즘 구상을 위해 계산법을 참고하였다. 1) 최대공약수 : 두 가지 숫자가 공통으로 갖는 공약수 중에 가장 큰 값. 2) 계산법 : 2) - ① 소인수분해법 : 주어진 두 숫자를 더 이상 나눌 수 없는 소인수 단위로 각각 분해한 후에, 공통된 소인수의 곱을 구하는 방법. * 예시 : 192와 72의 최대공약수 구하기 192 = 2 X 2 X 2 X 2 X 2 X 2 X 3 72 ..