yeolyi.com성열의 컴퓨터공학

체로 거르는 소수

최대공약수와 소수

화면 해상도 1,920 × 1,080을 16:9처럼 가장 작은 정수의 비로 줄이려면, 두 수를 모두 나누어떨어지게 하는 가장 큰 수로 나누면 됩니다. 1부터 1,080까지 두 수가 나누어떨어지는지 하나씩 확인하면, 1,080번 만에 가장 큰 120을 찾습니다. 더 빨리 찾을 수는 없을까요?

유클리드 호제법

두 수를 모두 나누어떨어지게 하는 수를 공약수(common divisor), 그중 가장 큰 것을 최대공약수(greatest common divisor, GCD)라 합니다.

유클리드 호제법(Euclidean algorithm)은 (a, b)를 (b, a mod b)로 바꾸기를 a를 b로 나눈 나머지 a mod b가 0이 될 때까지 되풀이하는 방법입니다. 그때의 b가 최대공약수입니다.

a를 b로 나눈 몫을 q, 나머지를 r이라 합시다.

a = b × q + r

(a, b)를 (b, r)로 바꿔도 되는 까닭은 두 쌍의 공약수가 같기 때문입니다. d가 a와 b의 공약수라면 a = d × x, b = d × y로 쓸 수 있으니 r도 d의 배수입니다.

r = a − b × q = d × (x − y × q)

거꾸로 d가 b와 r의 공약수라 b = d × y, r = d × z이면 a도 d의 배수입니다.

a = b × q + r = d × (y × q + z)

두 쌍의 공약수가 모두 같으니 그중 가장 큰 최대공약수도 같습니다.

a
b
나머지 연산 0번

(1,920, 1,080)에서 시작합니다.

각 줄의 b와 r이 다음 줄의 a와 b가 됩니다.

1,080번 걸리던 일이 나머지 연산 4번이면 끝납니다. 빨리 끝나는 까닭은 a mod b가 늘 a의 절반보다 작기 때문입니다. b가 a의 절반 이하면 나머지는 b보다 작고, 절반보다 크면 나머지는 a − b입니다. 그래서 두 번 나눌 때마다 큰 수가 절반 아래로 줄어, 나머지 연산은 O(log a)번이면 끝납니다.

에라토스테네스의 체

100 이하의 소수를 모두 구할 때 수마다 나눠 볼 수도 있지만, 지워 나가면 더 빠릅니다. 2를 남기고 2의 배수를 모두 지웁니다. 지워지지 않은 다음 수 3을 남기고 3의 배수를 지웁니다. 지워지지 않은 가장 작은 수는 자기보다 작은 어느 소수로도 나누어떨어지지 않으니 소수입니다. 이 방법을 에라토스테네스의 체(sieve of Eratosthenes)라 합니다.

지운 수 0개

1은 소수가 아니라 빼고 2부터 시작합니다.

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

하이라이트된 칸이 이번에 남기는 소수, 줄 그어진 칸이 지운 수입니다.

p의 배수는 p × p부터 지웁니다. p × 2, p × 3처럼 그보다 작은 배수는 더 작은 소수의 배수라 이미 지워졌습니다. 그래서 11 × 11이 100을 넘으면 멈춰도 됩니다.

마무리

탐색 글에서 본 것처럼 같은 일도 데이터를 어떻게 정리해 두느냐에 따라 빠르기가 달라집니다. 그래서 다음 파트에서는 값 여러 개를 메모리에 놓는 방법, 자료구조를 하나씩 다룹니다. 첫 글은 배열입니다.

도전 문제

a > b ≥ 1인 두 정수에 유클리드 호제법을 쓰면 나머지가 0이 나올 때까지 나머지 연산을 되풀이합니다. 나머지 연산을 정확히 7번 하는 경우 중 a가 가장 작을 때, a는 얼마일까요? 숫자로 답하세요.