13 / 16강

나머지로 줄이는 정수 문제

24개와 18개의 물건을 남김없이 같은 개수씩 묶으려 합니다. 한 묶음의 최대 크기는 두 수의 **최대공약수(GCD)**입니다. 1부터 하나씩 모두 나눠 보지 않고도 구할 수 있습니다.

유클리드 알고리즘

a = b × 몫 + 나머지입니다. a와 b를 함께 나누는 수는 그 나머지도 나눕니다. 반대로 b와 나머지를 나누는 수는 a도 나눕니다. 따라서 gcd(a, b) = gcd(b, a % b)입니다.

def gcd(a, b):
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(24, 18))
print(gcd(0, 7))

출력은 6, 7입니다. 첫 계산은 (24,18) → (18,6) → (6,0)으로 줄어듭니다. 나머지가 0이면 남은 수가 답입니다. 이 함수는 음수를 절댓값으로 바꾸고 gcd(0,0)은 관례에 따라 0으로 반환합니다.

소수는 어디까지 나눠 볼까요?

2 이상의 정수가 1과 자기 자신 외에 약수가 없으면 소수입니다. 합성수 n = a × b에서 a와 b가 모두 √n보다 클 수는 없습니다. 따라서 2부터 √n까지만 약수가 있는지 확인해도 됩니다. 정수 코드에서는 d*d <= n으로 범위를 판단할 수 있습니다.

1은 소수가 아닙니다. 소수 목록이 필요하다면 각 수를 따로 검사하는 대신, 에라토스테네스의 체로 이미 찾은 소수의 배수를 지울 수 있습니다. 체에서는 p²보다 작은 p의 배수가 앞 단계에서 처리되었다는 사실을 이용합니다.

문제 조건을 빠뜨리지 않습니다

• 최대공약수의 입력에 0이나 음수가 들어오는지 정합니다.
• 소수 검사는 2보다 작은 입력을 먼저 제외합니다.
• 제곱근으로 범위를 줄여도 정수의 자릿수가 매우 크면 비용이 커집니다. 반복 횟수와 큰 정수 연산 비용은 구분합니다.

확인 문제

49를 검사하면서 2부터 6까지만 나누어 보고 소수라고 결론 내리면 왜 틀릴까요?