• https://namu.wiki/w/유클리드 호제법
• https://ko.wikipedia.org/wiki/유클리드_호제법

두 양의 정수의 최대공약수를 구하는 방법

$$ 12345=1234 \cdot 10+5 \\ 1234=5 \cdot 246+4 \\ 5=4 \cdot 1+1\\ 4=1 \cdot 4\\ \therefore gcd(12345, 1234)=1 $$

큰 수를 작은 수로 나누고, 다시 나머지로 나누는 과정을 반복. 마지막으로 남은 수가 두 수의 최대공약수

• 재귀보다는 반복문을 사용

Code

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }
    return a
}

func gcdMultiple(nums []int) int {
    result := nums[0]
    for i := 1; i < len(nums); i++ {
        result = gcd(result, nums[i])
    }
    return result
}