최대공약수

최대 공약수(GCD. Greatest Common Divisor)는 둘 이상의 공약수 중에서 최대인 수입니다.

최대 공약수 로직

큰값을 작은값으로 나눈 나머지와 작은값을 나누어도 최대공약수는 같다
큰 값이 작은 값으로 나누어 떨어지면 작은값이 최대공약수

1. 큰 값, 작은 값을 정렬한다.
2. 큰 값을 작은 값으로 나눈 나머지가 0이면 작은 값이 최대 공약수, 0이 아니면 나눈 나머지와 기존에 작은 값을 다시 정렬 해서 나머지가 0이 될 때까지 다시 나눈다. >> 재귀 함수로 만들 수 있다.
3. 나머지가 1이면 최대공약수는 1
4. 최대공약수를 구해서 값이 엄청 클 경우를 대비 해 제곱근을 구한다.
5. 제곱근이 없으면? 예를 들면 12 >> Math.floor(Math.sqrt(12)) = 3으로 나누고 몫이랑 1,12로 목록을 만든다.
6. 제곱근으로 안떨어지면(12를 제곱근하면 4가 나오는 것처럼) 그 값과 최대공약수를 제곱근으로 나눈 나머지를 각각 제곱근을 구해서 최대공약수를 구한다.. 배열에 담는다. >> 제곱근 만드는 함수를 만든다.