직관 — 같은 답을 가진 작은 문제로 바꾼다
두 길이를 남김없이 나누는 가장 긴 단위를 찾고 싶다. 긴 길이에서 짧은 길이를 여러 번 떼어내고 남은 부분을 본다. 원래 두 길이를 모두 나누던 단위라면 남은 길이도 나눌 수 있다.
이 성질을 이용하면 최대공약수를 더 작은 정수 문제로 바꿀 수 있다. 또 소수를 찾을 때는 이미 아는 소수의 배수를 지워 후보를 줄일 수 있다. 소인수분해의 결과를 구하기 전에, 정수의 성질로 절차가 맞는 이유부터 확인하자.
정수 문제의 알고리즘은 계산에서 유지되는 성질을 이용한다
이 글은 최대공약수를 구하는 유클리드 호제법과 소수 목록을 구하는 에라토스테네스의 체를 다룬다. 두 알고리즘은 출력이 다르지만, 답을 잃지 않고 문제의 크기를 줄이는 이유를 설명할 수 있다. 호제법(互除法)은 두 수를 ‘서로 나눈다’는 뜻이다.
양의 정수 를 나누면 몫 와 나머지 는
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 현재 정수 쌍 | current pair | 처음에는 양의 정수, 종료 검사에서는 b=0 허용 | |
| 몫, 나머지 | quotient, remainder | 식 (1)의 정수 | |
| 나머지 연산 | modulo | b>0일 때 a를 b로 나눈 나머지 | |
| 최대공약수 | greatest common divisor | 두 수의 가장 큰 양의 공약수 | |
| 탐색 상한 | upper bound | 소수를 찾을 범위의 끝인 정수, N≥2 | |
| 체의 현재 후보 | sieve candidate | 배수를 지울지 검사하는 2 이상의 정수 | |
| 남은 후보 집합 | candidate set | 지워지지 않은 2부터 N까지의 정수 |
유클리드 호제법에서 최대공약수는 왜 보존될까?
의 공약수는 도 나눈다. 반대로 의 공약수는 도 나눈다. 양쪽의 양의 공약수 집합이 같으므로
예를 들어 이므로 252와 198의 공약수는 198과 54의 공약수와 같다. 다음 계산을 이어 가면
마지막 양의 나머지 18이 답이다. 모든 양의 정수는 0을 나누므로 에서 다. 따라서 마지막 쌍 (18,0)의 답을 처음 쌍까지 그대로 되돌릴 수 있다.
그림 1은 식 (3)을 넓이로 본 것이다. 가로 252, 세로 198인 직사각형에서 짧은 변을 한 변으로 하는 정사각형을 떼어 내고, 남은 직사각형에서 같은 일을 되풀이한다. 떼어 낸 정사각형의 개수 1, 3, 1, 2가 식 (3)의 몫이고, 한 변 198, 54, 36, 18이 차례로 나누는 수다.
figures/euclid_rectangle.py마지막 정사각형의 한 변 18은 36, 54, 198, 252를 모두 나누므로, 그림 1 전체를 한 변 18인 정사각형으로 빈틈없이 덮을 수 있다. 직관에서 말한 ‘두 길이를 남김없이 나누는 가장 긴 단위’가 바로 이것이다.
[정의] GCD(a, b): # 처음 a,b는 양의 정수
[반복] b ≠ 0인 동안:
r ← a mod b
a ← b
b ← r
[반환] a
나머지를 먼저 저장해야 원래 a,b로 계산한 값이 남는다. a ← b부터 수행하고 새 a로 나머지를 구하면 이 되어 다른 절차가 된다.
그림 2는 0 검사 뒤에만 나머지를 계산하도록 분리했다. 첫 a가 b보다 작아도 첫 나머지는 a이므로 다음 쌍에서 순서가 바뀌어 진행된다.
figures/euclid_flow.py새 나머지는 늘 이전의 두 번째 수보다 작다. 0 이상의 정수를 엄격하게 계속 줄이는 과정을 무한히 이어 갈 수 없으므로 반드시 0에 도달한다. 식 (2)는 정확성, 이 감소는 종료의 일반 근거다. 재귀 형태로도 같은 쌍을 호출할 수 있다.
유클리드 호제법에서 나머지가 0이면 답도 0인가요?
아니다. 마지막 쌍 (18,0)의 최대공약수는 18이다. 나머지 0은 ‘이제 나누어떨어져 반복을 끝낸다’는 표시이지 출력할 최대공약수가 아니다.
유클리드 호제법에 처음부터 0을 넣을 수 있나요?
유클리드 호제법은 한 수만 0이고 다른 수가 양수이면 그 양수를 그대로 답으로 돌려주도록 확장할 수 있다. 이기 때문이다. 둘 다 0이면 모든 양의 정수가 공약수라서 가장 큰 공약수가 없으므로 이 정의에서는 제외한다.
유클리드 호제법은 소인수분해보다 무엇이 편할까?
소인수를 찾지 않고 나눗셈만 되풀이하므로, 소인수분해가 어려운 수에서도 몇 번 만에 끝난다. 3127과 2491은 나눗셈 4번으로 최대공약수 53을 얻는다.
실제로 , 이다. 소인수분해로 같은 답을 얻으려면 2491은 47이 나올 때까지 소수 15개로, 3127은 53이 나올 때까지 소수 16개로 나누어 봐야 한다.
최대공약수 를 알면 최소공배수 도 바로 구한다. , 이고 14와 11은 공약수가 1뿐이다. 두 수를 모두 담는 가장 작은 수는 공통 부분 18을 한 번만 쓴 이다.
곱 에는 공통 부분 가 두 번 들어 있으므로 한 번 나눈 것이다. 분수 의 분자와 분모를 18로 나누면 한 번에 기약분수 이 된다.
에라토스테네스의 체는 왜 소수만 남길까?
체는 각 단계의 p 자신은 남기고 그보다 큰 배수만 지운다. 소수는 자신보다 작은 2 이상 수의 배수가 아니어서 끝까지 남고, 합성수는 가장 작은 소인수의 단계에서 지워진다. 후보는 2부터 N까지이고 p=2부터 차례로 이 일을 한다. 이미 지워진 p는 합성수이고 그 배수는 p의 소인수 단계에서 지워지므로 새로 지울 필요가 없다. 1은 처음부터 후보에 넣지 않는다.
여기서는 불필요한 중복 제거를 줄여 부터 지운다. 는 p보다 작은 인수의 소인수를 가지므로 이전 단계에서 이미 지워졌다. p 자신은 소수일 수 있어 지우지 않는다.
[정의] SIEVE(N): # 정수 N ≥ 2
S ← {2, 3, …, N}
p ← 2
[반복] p × p ≤ N인 동안:
[조건] p가 S에 남아 있으면:
p×p, p×p+p, p×p+2p, … 중 N 이하를 S에서 지운다
p ← p + 1
[반환] S를 작은 순서로 나열한 목록
그림 3은 N=35에서 이 절차를 수행한 결과다. 2의 제곱 4, 3의 제곱 9, 5의 제곱 25부터 배수를 지우고, 에서 반복을 멈춘다. 2 단계에서 16개, 3 단계에서 새로 5개, 5 단계에서 새로 2개를 지워 합성수 23개가 사라지고 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31이 남는다.
figures/sieve_candidates.py에라토스테네스의 체는 왜 제곱근 이하의 수까지만 처리할까?
N 이하의 합성수는 반드시 이하의 소인수를 가지기 때문이다. 그래서 그림 3에서 7 이상의 소수 단계를 하지 않았는데도 35 이하의 합성수가 모두 지워졌다.
합성수 에 두 인수 이 있고 라 하자. 둘 다 보다 크면 이 되므로, 적어도 한 인수는 이하다. 따라서 그 인수의 소인수 는 , 곧 을 만족한다. 그러므로 인 후보를 모두 처리하면 모든 합성수가 지워진다. 지우는 수는 두 2 이상 정수의 곱이므로 소수는 지워지지 않는다.
그림 4는 36의 약수를 곱이 36인 짝으로 이은 것이다. (1,36), (2,18), (3,12), (4,9), (6,6)의 다섯 짝 모두 한쪽이 이하에 있다. 짝의 한쪽이 6보다 크면 곱이 36이 되도록 다른 쪽은 6보다 작아진다. 유한한 그림의 검산과 모든 N에 대한 위의 논증을 구별한다.
figures/divisor_pairs.py정수 문제의 알고리즘은 답 보존과 종료를 함께 확인한다. 양의 정수 a,b에는 gcd(a,b)=gcd(b,a mod b)를 반복하고, 정수 N≥2의 체는 p²≤N인 후보를 처리해 합성수를 지우되 p 자신을 남긴다.
에라토스테네스의 체는 각 후보를 일일이 나누나요?
아니다. 체는 배수의 위치를 지우는 절차다. 예를 들어 5 단계에서는 25, 30, 35를 표시하며, 이미 지워진 30을 다시 지워도 남는 소수 목록은 바뀌지 않는다.
에라토스테네스의 체처럼 소수 판정도 제곱근까지만 나누어 보면 되나요?
그렇다. 2 이상의 정수 이 이하의 어떤 소수로도 나누어떨어지지 않으면 은 소수다. 91은 이라 2, 3, 5, 7만 확인하면 되고 7로 나누어떨어져 합성수다. 97은 네 수 모두로 나누어떨어지지 않아 소수다.
정수 문제의 알고리즘에서 생기는 오해
- 나머지를 계산할 때 b=0도 허용한다 — 0으로 나눌 수 없다. 순서도의 종료 검사가 먼저여야 한다.
- 체는 p부터 배수를 모두 지우면 된다 — 그러면 소수 p까지 지운다. 자신을 남기고 적어도 2p 이후를 지워야 하며, 위 개선 절차는 이미 지운 수를 건너뛰어 p²부터 시작한다.
직접 해보기
- 330과 126의 최대공약수를 각 나눗셈과 함께 구하자.
답
, , , , , , 이다. 나머지 계산은 7번이며 답은 6이다.
- GCD에 (42,70)을 넣으면 첫 두 쌍은 어떻게 바뀌는가? 최종 답은?
답
라서 (70,42)가 되고, 이라서 (42,28)이 된다. 이어 (28,14), (14,0)이므로 답은 14다.
- 체로 40 이하의 소수를 구하자. 35 이하 목록과 비교해 새로 남는 수는 무엇인가?
답
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37이다. 새 소수는 37 하나다. 36, 38, 39, 40은 각각 2 또는 3의 배수로 지워진다.
- N=49에서 반복 조건을 p²<N으로 잘못 적으면 어떤 합성수가 남는가?
답
일 때 7 단계를 수행하지 않아 49가 남는다. 49의 유일한 소인수는 7이므로 앞의 소수 단계로는 지워지지 않는다. 등호를 포함한 이 필요하다.
- 문제 1의 결과로 330과 126의 최소공배수를 구하고, 분수 을 기약분수로 나타내자.
답
최대공약수가 6이므로 식 (5)처럼 이다. 분자와 분모를 6으로 나누면 이고, 21과 55의 공약수는 1뿐이다.
더 읽기
- 교육부 고시 제2022-33호 — 별책20 [12이수02-05]의 체·유클리드 호제법과 절차의 수행·반성.
- 우리교과서 『이산 수학』 공개 원문 — 인쇄71–74쪽의 최대공약수, 소수 제거와 나머지 순서도. 이 글은 새 정수 쌍과 N=35를 쓰고 체의 p² 시작 조건을 증명했다.
영상 노트
- 00:00 나머지로 바꿔도 공약수가 같을까?
- 00:40 식 (1)의 양방향 나눗셈 성질로 식 (2) 설명하기
- 01:20 식 (3)을 그림 1의 정사각형 떼어 내기로 보기
- 02:00 그림 2의 저장 순서대로 의사코드 수행하기
- 02:45 식 (4)의 큰 수와 식 (5)의 최소공배수·기약분수
- 03:40 그림 3에서 p²부터 지우는 이유와 단계별 제거 확인하기
- 04:20 그림 4의 약수 짝으로 제곱근 상한 설명하기
- 05:10 N=49에서 잘못된 부등호 반성하기
지도에서의 위치
- 2026-11-16 · 독립 검수 NT1 — 핵심 요약에 허용 입력 조건을 명시함
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 호제법의 넓이 모형, 큰 수의 호제법과 최소공배수·기약분수 활용, 약수 짝으로 본 제곱근 상한, 체의 단계별 제거와 소수 판정 질문, 해보기 5문항 보강, 약수 짝 그림을 같은 간격 배치로 정리 (에이전트 수정, 그림 2→4)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림