mir.pe (일반/밝은 화면)
최근 수정 시각 : 2024-12-25 01:05:35

소수(수론)

프라임 넘버에서 넘어옴


파일:나무위키+유도.png  
은(는) 여기로 연결됩니다.
0과 1 사이의 실수\에 대한 내용은 소수(기수법) 문서
를
의 번 문단을
의 부분을
, 에 대한 내용은 문서
를
의 번 문단을
의 번 문단을
의 부분을
의 부분을
, 에 대한 내용은 문서
를
의 번 문단을
의 번 문단을
의 부분을
의 부분을
, 에 대한 내용은 문서
를
의 번 문단을
의 번 문단을
의 부분을
의 부분을
, 에 대한 내용은 문서
를
의 번 문단을
의 번 문단을
의 부분을
의 부분을
, 에 대한 내용은 문서
를
의 번 문단을
의 번 문단을
의 부분을
의 부분을
, 에 대한 내용은 문서
를
의 번 문단을
의 번 문단을
의 부분을
의 부분을
, 에 대한 내용은 문서
를
의 번 문단을
의 번 문단을
의 부분을
의 부분을
, 에 대한 내용은 문서
를
의 번 문단을
의 번 문단을
의 부분을
의 부분을
, 에 대한 내용은 문서
를
의 번 문단을
의 번 문단을
의 부분을
의 부분을
참고하십시오.
정수론
Number Theory
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px" 		공리
페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질
산술
나눗셈 약수· 배수 배수 · 약수( 소인수) · 소인수분해( 목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수
약수들의 합에 따른 수의 분류 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수
정리 베주 항등식 · 산술의 기본정리 · 나눗셈 정리
기타 유클리드 호제법 · 서로소
디오판토스 방정식 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결)
모듈러 연산
잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리
소수론
수의 분류 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수( 사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수
분야 대수적 정수론( 국소체) · 해석적 정수론
산술함수 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식
정리 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)( 천의 정리) · 폴리냑 추측(미해결) · 소수 정리
기타 에라토스테네스의 체 · 윌런스의 공식
}}}}}}}}} ||

수 체계
Number Systems
{{{#!wiki style="margin:0 -10px -5px; min-height:calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-5px -1px -11px; word-break: keep-all" 		사원수 [math(\mathbb H)] · 팔원수 [math(\mathbb O)]
↑ 확장 ↑
복소수 [math(\mathbb C)]
↑ 대수적 폐포, 행렬 표현, 순서쌍 구성 등 ↑ 허수 [math(\mathbb{C}
실수 [math(\mathbb R)]
↑ 완비화, 데데킨트 절단 등 ↑ 무리수 [math(\mathbb{R} \setminus \mathbb{Q} = \mathbb I)]
유리수 [math(\mathbb Q)]
↑ 곱셈의 역원 ↑ 정수가 아닌 유리수 [math(\mathbb{Q} \setminus \mathbb{Z})]
정수 [math(\mathbb Z)]
↑ 덧셈의 역원 ↑ 음의 정수 [math(\mathbb{Z} \setminus \mathbb{N})]
범자연수 [math(\mathbb N_0)]
↑ 자연수의 집합론적 구성 ↑
[math(0)]
소수 [math(\mathbb P)] · 초실수 [math(\mathbb R^{\ast})] · 대수적 수 [math(\mathbb A)]( 대수적 무리수 [math(\mathbb{A} \cap \mathbb{I})]) · 초월수 [math(\complement {\mathbb A})] · 벡터 공간 [math(\mathbb V)] · 이원수 · 분할복소수 }}}}}}}}}


1. 개요2. 역사3. 성질
3.1. 관련 미해결 문제
4. 학생들을 위한 부연5. 표기 문제6. 소수와 알고리즘, 암호7. 소수 판정법 및 소인수분해8. 여담

1. 개요

素 數 / prime number

1, -1과 자기 자신, 자기 자신의 반수[1]로밖에 나누어떨어지지 않는 1 이외의 정수, 즉 양의 약수가 2개인 자연수를 의미한다.[2]

소수의 정의는 '1과 자기 자신으로밖에 나누어 떨어지지 않고 자기 자신의 곱셈의 역수가 없는 수'이다.[3]

많은 사람들이 [소수]로 잘못 읽으나, 본래는 사잇소리 현상을 적용하여 [소쑤]라고 읽어야 맞다. 0.1, 0.2, 0.3 같은 소수와는 발음이 달라 동음이의어 관계가 아니다. 굳이 따지자면 동철이음이의어 관계로 표기로는 구분되지 않으나 발음으론 구분된다. 그래서 연배가 있는 교수들은 사잇소리 현상이 일어남을 나타내기 위해 '솟수'라고 사이시옷을 넣는 표기를 쓰는 경우도 있다. 그리고 사이시옷이 들어간 이 '솟수'라는 표기가 인정된다면 [소쑤]가 원칙 발음이되 [솓쑤]도 허용 발음이 된다.

2. 역사

소수를 정의하고, 이에 관해 연구에 본격적으로 매달린 것은 고대 그리스인들이다. 수학을 연구한 몇몇 그리스 학파들은 수학을 단순한 학문을 넘어서, 종교적인 의미로 받아들였다. 가령 우주가 모두 기하학과 수로 이루어져 있다는 신앙이 대표적이다. 현대인이 보기에는 터무니없지만, 그들은 그 중에서 오로지 자연수만이 우주를 구성하는 참된 숫자라고 믿었다. 그렇기 때문에 자연수의 성질을 연구하는 것은 단순히 숫자 놀음을 하는 것이 아니라, 우주의 근본원리를 탐구하는 것이라고 여겼다.

이 맥락에서 소수는 가장 신비롭고, 근본적인 것으로 믿어졌다. 고대 그리스 수학자들이 보기에 소수는 숫자의 원소에 해당하는 것으로 보였기 때문이다. 우주는 자연수로 이루어져 있는데, 모든 자연수는 소수로부터 파생이 되었기 때문이다. 그래서 소수의 완전한 목록을 만드는 것은 곧 현대 화학의 원소 주기율표를 완성하는 것 만큼 중요한 것이 되었다. 그래서 에라토스테네스는 에라토스테네스의 체라는 일종의 알고리즘을 만들었고, 유클리드 또한 똑같은 믿음을 가지고 소수에 대해서 연구했다.

반면에 자연수가 우주를 구성한다는 종교를 가지지 않았던 다른 문화권에서는 소수에 대한 연구에 그다지 관심이 없었다. 바로 옆의 바빌론이나 이집트는 수학으로 높은 명성을 떨쳤지만, 오히려 후배인 고대 그리스에 비하면 연구성과가 없다시피 했다.

3. 성질

쌍둥이 소수는 p, p+2 모두 소수가 되는 순서쌍이다. 사촌 소수는 차가 4, 섹시 소수는 차가 6이 되는 소수 순서쌍이다.

2는 유일한 짝수 소수이다. 즉, 2를 제외한 모든 짝수는 합성수이며, 2를 제외한 소수는 모두 홀수이다. 사실 개요문단의 정의는 prime이 아닌 irreducible에 대한 정의이다. 소수(prime)의 실제 정의는 임의의 정수 a, b에 대해 p|ab이면 p|a or p|b를 만족할 때 p를 prime이라고 한다. 정수 집합에서는 이 정의가 같아서 상관없지만, 대수적 정수론에서는 irreducible이지만 prime이 아닌 경우가 존재한다.[4]

소수가 아니고 곱셈의 역수가 없는 수를 합성수(composite number)라고 한다. 쉽게 이해하기 위해 소수를 ' 약수가 2개인 수'로 정의하기도 한다. 참고로 1은 1과 자기 자신(1)으로만 나눠떨어지긴 하지만, 곱셈의 역수가 있는 1을 소수로 인정하면 소인수분해의 유일성이 사라지는 등의 문제로 인해 1은 소수가 아닌 것으로 약속했다. 따라서 1은 자연수이지만 소수도 아니고 합성수도 아니다.[5] 비슷하게 일반적인 1을 갖는 가환환 위에서도 곱셈의 역수를 가지는 원소는 소수도 합성수도 아닌 것으로 약속한다.

참고로 유리수와 같이 0 말고 모두 곱셈의 역수를 가지고 있는 경우는 모든 원소가 irreducible도 prime도 아니다. 이 두 개념은 0도 아니고 단위원[6]도 아닌 원소에 대해서만 정의되기 때문이다.

집합 기호로는 볼드체를 사용한 [math(\bold P)]나 칠판체를 사용한 [math(\mathbb P)]로 나타낸다.

기본적으로 모든 사칙연산에 대해 닫혀 있지 않다.[7]
후술할 소수 나열에선 알기 힘들지만 수가 커질수록 소수의 빈도는 점점 감소하며, 소수가 없는 아주 긴 구간들의 출현 빈도들이 높아진다. 이렇게 되면 계속 가다가 소수가 없는 구간의 길이가 1000조를 넘는다든가 심지어 언젠가는 아예 G(64)를 넘을 수 있다.[8] 이쯤 되면 결국 나중엔 소수가 절대 나오지 않게 되는 게 아닌가 하는 추측도 나올 수 있겠지만, 유클리드에 의해 소수는 무한히 많이 있다는 것이 증명되었다.[9] 오일러는 소수의 역수의 합이 발산한다는, 좀 더 강력한 정리를 증명했다.[10] 더 나아가 2 이상의 자연수 [math(n)]에 대해 [math(n<p<2n)]을 만족하는 소수 [math(p)]가 항상 존재한다(베르트랑-체비쇼프 정리). 이 정리는 '[math(n)]이 [math(N)] 이상의 자연수이면 [math(n<p<f(n))]을 만족하는 소수 [math(p)]가 항상 존재한다' 꼴의 변종이 많이 있으며, 1952년에는 [math(N=25,\;f(n)=\displaystyle \frac{6n}{5})]이 증명되었고 2016년에는 [math(N=468991632,\;f(n)=\displaystyle n+\frac{n}{5000 \ln^2 n})]이 증명되었다. 소수의 크기는 ' 자연수의 진부분집합인 무한집합'인 이상 자연수와 동일한 [math(aleph_0)]이다.

귀류법으로 소수가 유한하다고 가정하자. 그럼 그 소수들을 모두 나열한 목록 [math(p_1,\;p_2,\;p_3,\;\cdots,\;p_n)]을 생각할 수 있다([math(n)]은 소수의 개수). 이제 이 소수들을 몽땅 곱하고 1을 더한 수를 [math(N)]라고 하자. 즉, [math(N = p_1 p_2 \cdots p_n+1)]이다. 이때 [math(N)]은 [math(n)]개의 어떠한 소수로도(가정에 의하면, 모든 소수로) 나누어떨어지지 않으므로(1이 남으니까), [math(N)]가 새로운 소수이거나, 아니면 목록에 없는 새로운 소수로 나누어떨어질 수밖에 없다[11] 어느 쪽이든 간에 소수가 [math(n)]개뿐이라는 가정에 모순이므로 소수는 무한히 많다. 좀 더 자세한 내용은 네이버캐스트에서 다룬 글을 참조할 것[12]. 이 증명법은 수학자 에르되시 팔이 생전에 말한 '그 책'(신이 갖고 있는 증명법을 적은 책)에 들어갈 만하다고 할 정도이며, 실제로 '하늘책의 증명'이라는 책에 맨 처음에 들어가 있다. 수학의 전문 지식이 없는 일반인들조차 명쾌하게 이해할 정도로 매우 우아한 증명으로 이름높다.

한편 위상수학을 이용해서 소수의 무한성을 증명할 수도 있다. # 이 증명도 위에서 말한 '하늘책의 증명'에 수록되어있다. 일반인은 물론 수학도들에게도 기괴함과 동시에 감탄스러운 증명으로 꼽히며, 제법 유명해지면서부터는 각종 위상수학 교과서들이 연습문제로 사골처럼 우려먹는 클리셰가 되었고, 대학 수업에서도 과제나 시험문제 등으로 흥행하고 있다.

소수 정리를 통해 큰 수 [math(n)] 이하의 소수의 개수를 근사적으로 구할 수 있다.

2 이상의 모든 자연수는 한 개 이상의 소수들의 곱으로 유일하게 나타낼 수 있고( 산술의 기본 정리), 이 유일한 표현을 소인수분해라 한다. 어찌 보면 당연해 보이면서도 흥미로운 사실인데, 소수들의 성질만 연구해도 모든 정수의 성질을 알 수 있다는 의미이기 때문. 덕분에 소수는 자연수와 정수의 성질을 연구하는 정수론의 중심 탐구대상이었다.

3.1. 관련 미해결 문제

하지만 소수의 성질을 밝히는 것은 생각보다 매우 어렵다. 많은 수학자들이 위 무한한 소수들의 분포나 규칙성을 밝혀내려고 했지만, 어느 누구도 정답이라고 할 만한 패턴을 밝혀내진 못했다. 현재까지도 소수에 관련된 다음처럼 많은 문제들이 남아서 호기심을 자극한다. 특정한 꼴의 소수가 무한한가 또는 소수 간격의 상한에 관한 문제가 많다. 비록 수학의 미해결제가 많기는 하지만, 문제는 소수와 관련해서는 대부분의 문제들이 미해결이라는 것이다. 게다가 석사 정도는 되어야 이해라도 할 수 있는 다른 분야의 문제들과는 달리 중학생도 이해할 수 있을 만한 짧고 간결한 문제인데도![14] 다행히 '약한' 골드바흐의 추측은 2013년에 완전히 증명되었다. 해당 문서 참조.

현대 수학자들은 소수의 분포에 대해서 순수하게 무작위적이라는 가설을 세우고 있다. 소수의 개수는 특정 평균선을 기준으로 변동하는데, 그 변동하는 양에서는 주기성 같은 경향을 더 찾을 수가 없다는 이야기. 어떤 의미에서 이는 소수의 쉬운 패턴을 찾기란 힘들다는 사실을 암시한다. 물론 이런 이야기를 하는 수학자 자신들은, 이 믿음의 기초인 리만 가설에서조차 리만이 예견한 수준을 아직도 벗어나지 못하고 있다.

중국계 미국 수학자 장이탕이 증명한 바에 의하면 7000만 이하 차이가 나는 소수 쌍이 무한히 존재하며 후에 폴리매스 8 프로젝트를 통해 전 세계의 정수론 전문가들이 달려든 결과 차이가 246이하인 소수쌍이 무한하다는 것이 증명되었다. 지금까지 정수론에서 제기된 온갖 추측을 유리하게 가정해도 차이를 6 미만으로 줄일 수가 없어 정작 쌍둥이 소수 추측은 해당 방법으론 증명할 수 없다고 한다.

4. 학생들을 위한 부연

소수를 이야기할 때는 자연수만 생각하면 된다. 다시 말해 소수 이야기를 할 때는 음의 정수와 소수(decimal, 0.25 같은 것)는 생각하지 않아도 좋다.

예를 들어 “-3은 소수인가?”라는 질문은 그냥 “3은 소수인가?”라는 질문과 똑같은 것이다. 소수의 정의인 “1과 그 자신으로만 나눠진다”는 수의 음양을 고려하지 않는 기준이며, “3은 1, 3, -1, -3 네 수로 나눌 수 있으니 소수가 아니다” 같은 말을 해서는 안 된다. 원래 약수는 음양을 따지지 않는 것이다.[15]

간혹 학생들이 “ 십진법 이외의 진법에도 소수가 있나요?”라는 질문을 하는데, 소수뿐 아니라 수의 모든 성질은 수의 진법에 전혀 영향을 받지 않는다. 만약 학생이 그런 질문을 한다면 그 학생은 진법의 개념을 본질적으로 잘못 이해하고 있는 것이다. 진법은 오직 우리가 수를 표기하는 방법일 뿐이며 수의 본질(즉 수량)에 전혀 영향을 주지 않는다. 예를 들어 바둑돌 세 개의 개수를 십진수로 '3(10)'으로 표기하든 이진수로 '11(2)'으로 표기하든 실제 개수가 달라지는 것은 아니다.

만약 학생이 위의 설명을 이해하지 못한다면 실제로 십진법 외의 진법[16] 으로 소수를 나눠보도록 해 보자. 예를 들어 3을 2진법으로 나타낸 11(2) , 7을 5진법으로 나타낸 12(5) 모두 해당 진법으로 나눠보면 1과 그 자신 외의 수로는 나눠지지 않는 소수이다.

만약 십진법 이외의 진법으로 나눗셈 등의 사칙연산을 아직 할 수 없는 좀 더 저연령 학생인 경우, 바둑알이나 공 같은 물체를 이용하면 좋다. 학생에게 11을 바둑알로 표시해보라고 하자. 그러면 학생은 (일반적으로) 바둑알 11개를 일렬로 나란히 늘어놓을 것이다. 그러면 바둑알 10개만 남기고 끝의 바둑알 한 개를 떼어 그 윗줄로 옮겨주고, 아랫줄의 바둑알 10개가 “십”, 윗줄의 바둑알 한 개가 “일”, 합해서 “십 일”이며 이것이 바로 우리가 사용하는 십진법임을 이해시켜 주자. 이번에는 이 바둑알 11개를 7진법으로 나타내보라고 하자. 학생이 위의 설명을 이해했다면, 아랫줄에 바둑알 7개, 윗줄에 바둑알 4개를 늘어놓을 것이다. 즉 십진법 11은 7진법 14(7)임을 학생 스스로 이해할 수 있을 것이다. 그럼 이번에는 바둑알 12개로 같은 작업을 시켜보자. 십진법 12가 7진법 15(7)임을 학생이 이해할 수 있도록 해 주자.

이제 이 11개의 바둑알을 모아 학생에게 쥐어주고, 이를 서로 동일한 수의 바둑알들로 구성된 두 개 이상의 무더기로 등분해보라고 하자. 당연히 못 할 것이다. 그럼 이번에는 12개의 바둑알을 모아 동일한 작업을 시켜 보자. 바둑알 두 개씩 여섯 무더기(6x2), 세 개씩 네 무더기(4x3), 네 개씩 세 무더기(3x4), 여섯 개씩 두 무더기(2x6) 등 다양한 방법으로 등분할 수 있음을 학생이 알 수 있게 해 주자. 12와 같이 등분될 수 있는 수는 소수가 아니며, 11처럼 등분될 수 없는 수를 소수라 함을 이해시켜 주자.

또한 학생은 이를 통해, 11은 십진수로 11이라 표기하든 7진법으로 14(7)로 표기하든 간에 실제 수량은 변하지 않으며, 11이 등분될 수 없는 성질, 즉 1과 그 자신 이외의 수로 나눠질 수 있는 성질은 진법과 무관함을 이해할 수 있을 것이다.

5. 표기 문제

과거에는 ' 솟수'라고 표현했으나, 합성어가 한자와 한자의 결합으로 이루어져 있을 때에는 사잇소리 현상이 일어나더라도 사이시옷을 표기하지 않는 것으로 맞춤법을 고칠 때 6개의 예외[17]에 포함되지 않으며 '소수'로 바뀌었고, 그로 인해 0.1과 같은 소수(小數, decimal)와 동철이음이의어(同綴異音異義語)가 됐다. 소수(素數)의 표준 발음은 사잇소리 현상이 적용된 [소쑤]로, [소ː수]로 발음되는 소수(小數)와 명확히 구별된다. 그렇지만 대부분의 사람이 소수(素數)를 그저 표기대로 [소수]라고 발음하는 것이 문제. 같은 한자어인데도 치과(齒科)라는 표기를 알아서 [치꽈]로 읽는 경우와는 대조적이다. 결국 현실 발음으로는 구별이 거의 안 되는 데다가 표기 차원에서도 한글로 써 두면 전혀 구별할 방법이 없어 부득이하게 한자로 쓸 수밖에 없다.

일부 수학자들은 국어학자들이 언어 원칙을, 그것도 우리말 표기법의 아킬레스건이라는 악평을 듣는 사이시옷 원칙을 바탕으로 수학의 고유 용어인 솟수를 소수로 만들어버린 데에 큰 불만을 갖고 있으며, 소수(少數, Minority)와 소수(素數, Prime), 소수(小數, Decimal)를 우리글로는 구별할 수 없는 상황을 정상이라고 보지 않는다. 심지어 20세기에는 솟수가 한자어가 아니라 "솟아오른 수"라는 의미라는 주장까지 펼치며[18] 솟수가 소수로 개명되는 것을 막으려 하기까지 했다.

북한의 문화어로는 ‘씨수’라고 하며, 한국에서도 용어를 ‘씨수’로 바꾸자고 주장하는 수학자들이 있다. 발음이 다르고 용법이 다르다고는 하지만 어쨌든 표기가 동일한 것이 있으면 헷갈리는 것이 당연하기 때문에, 소수의 용어나 발음 문제는 가끔 등장하는 해묵은 이야기이기도 하다.

일본에서도 같은 용어를 쓰지만 小数(しょうすう)와 素数(そすう)로 발음도 다를 뿐더러 애초에 한자로 표기하기 때문에 문제가 안 된다.[19] 중국에서는 소수(素數)를 质数(zhìshù, 질수)라고 한다.

참고로 복소수(複素數, Complex Number)는 소수(素數, Prime Number)와는 관련이 없다. 복소수는 실수와 허수의 두 원소의 합으로 이루어진 수 집합으로, 소수의 범주보다 아득히 위에 있다. 그러나 해석적 정수론의 등장으로 이 둘의 연결고리가 생기긴 했다. 다만 그게 악명 높은 리만 가설이라 그렇지.

6. 소수와 알고리즘, 암호

소수는 전통적으로 순수수학만의 영역에 속했지만, 20세기 후반 암호학과 컴퓨터의 발전으로 현실과 밀접한 관련을 맺고 있다.

공개열쇠 암호 체계(public-key cryptography)는 '암호화는 쉽지만 해독하기는 어렵다'라는 개념을 도입해 암호체계의 안정성을 높이는데, 이에 적합한 '연산은 쉬운데 역연산은 어려운' 예가 소인수분해인 것이다. 이 소인수분해의 특성을 쓰는 RSA 암호 체계는 아주 큰 소수 [math(p)]와 [math(q)]의 곱 [math(pq)]를 이용해 암호화를 하지만, 해독하려면 [math(p)]와 [math(q)] 각각이 필요하다. 예로 다섯 자리 숫자 둘을 곱하는 건 손으로도 금방 하지만, [math(pq=1459160519)]만 알려주고 p와 q의 쌍(=34583×42193)을 찾으라고 한다면 꽤 삽질이 필요할 것이다. 실제로 RSA에 쓰는 수가 몇 백여 자리의 소수들이다.

덕분에 이런 아주 큰 소수를 찾고 그 수가 소수인지 아닌지를 정하는 소수 판정법과, 역시 큰 수를 소인수분해하는 알고리즘이 중요한 이슈로 떠올랐다.

7. 소수 판정법 및 소인수분해

어떤 수가 소수임을 판정하기는 어렵다. 가장 간단하게 생각할 수 있는 방법은 2부터 [math(\sqrt n)]까지의 소수로 모두 나누어 보는 것이다.[20] 하지만 n이 50여 자리만 되어도 나눗셈을 몇 번 해야 되는지는 상상만 해도 끔찍하다.

1부터 n까지 모든 소수를 찾는 방법으로 고대 그리스의 수학자 에라토스테네스가 만들어 낸 방법이 있는데, 이는 하나의 수가 소수인지 아닌지를 판정하는 것보다는, 일정 범위 내의 소수를 모두 찾아내는 데 이용하는 경우가 많다. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 ' 에라토스테네스의 체'라고 부른다. 과정은 아래와 같다.
  1. 찾아내고 싶은 범위만큼 자연수를 죽 늘어놓는다.
  2. 1은 수학적으로 소수도, 합성수도 아닌 유일한 자연수이므로 먼저 1을 지운다.
  3. 먼저 2를 소수로 표시하고 2를 제외한 2의 배수(4, 6, 8, ...)를 모두[21] 소거한다.
  4. 그 다음 3을 소수로 표시하고 남아있는 수 중 3을 제외한 3의 배수(9, 15, 21, ...)도 모두[22] 소거한다.
  5. 그 다음 5를 소수로 표시하고 남아있는 수 중 5를 제외한 5의 배수(25, 35, 55, ...)도 모두[23] 소거한다.
  6. 그 다음 7을 소수로 표시하고 남아있는 수 중 7을 제외한 7의 배수(49, 77, 91, ...)도 모두[24] 소거한다.
  7. 남아있는 가장 작은 수(소수)에 대해 이 과정을 [math(\sqrt n)] 보다 작거나 같은 소수까지 계속 반복한다.
이렇게 하다 보면 [math(n)]보다 작은 소수만 남는다. 아래 그림은 에라토스테네스의 체로 1에서 100까지의 수 중 소수를 찾아낸 예이다.
[math(\begin{array}{|c|c|c|c|c|c|c|c|c|c|}\hline
\cancel1 & \bf\color{red}2 & \bf\color{blue}3 & \cancel{\color{red}4} & \bf\color{green}5 & \cancel{\color{purple}6} & \bf\color{magenta}7 & \cancel{\color{red}8} & \cancel{\color{blue}9} & \cancel{\color{red}1\color{green}0} \\
\hline
\bf11 & \cancel{\color{purple}12} & \bf13 & \cancel{\color{red}1\color{magenta}4} & \cancel{\color{blue}1\color{green}5} & \cancel{\color{red}16} & \bf17 & \cancel{\color{purple}18} & \bf19 & \cancel{\color{red}2\color{green}0} \\
\hline
\cancel{\color{blue}21} & \cancel{\color{red}22} & \bf23 & \cancel{\color{purple}24} & \cancel{\color{green}25} & \cancel{\color{red}26} & \cancel{\color{blue}27} & \cancel{\color{red}2\color{magenta}8} & \bf29 & \cancel{\color{purple}3\color{green}0} \\
\hline
\bf31 & \cancel{\color{red}32} & \cancel{\color{blue}33} & \cancel{\color{red}34} & \cancel{\color{green}3\color{magenta}5} & \cancel{\color{purple}36} & \bf37 & \cancel{\color{red}38} & \cancel{\color{blue}39} & \cancel{\color{red}4\color{green}0} \\
\hline
\bf41 & \cancel{\color{purple}4\color{magenta}2} & \bf43 & \cancel{\color{red}44} & \cancel{\color{blue}45} & \cancel{\color{red}46} & \bf47 & \cancel{\color{purple}48} & \cancel{\color{magenta}49} & \cancel{\color{red}5\color{green}0} \\
\hline
\cancel{\color{blue}51} & \cancel{\color{red}52} & \bf53 & \cancel{\color{purple}54} & \cancel{\color{green}55} & \cancel{\color{red}5\color{magenta}6} & \cancel{\color{blue}57} & \cancel{\color{red}58} & \bf59 & \cancel{\color{purple}6\color{green}0} \\
\hline
\bf61 & \cancel{\color{red}62} & \cancel{\color{blue}6\color{magenta}3} & \cancel{\color{red}64} & \cancel{\color{green}65} & \cancel{\color{purple}66} & \bf67 & \cancel{\color{red}68} & \cancel{\color{blue}69} & \cancel{\color{red}7\color{green}0} \\
\hline
\bf71 & \cancel{\color{purple}72} & \bf73 & \cancel{\color{red}74} & \cancel{\color{blue}7\color{green}5} & \cancel{\color{red}76} & \cancel{\color{magenta}77} & \cancel{\color{red}78} & \bf79 & \cancel{\color{red}8\color{green}0} \\
\hline
\cancel{\color{blue}81} & \cancel{\color{red}82} & \bf83 & \cancel{\color{purple}8\color{magenta}4} & \cancel{\color{green}85} & \cancel{\color{red}86} & \cancel{\color{blue}87} & \cancel{\color{red}88} & \bf89 & \cancel{\color{purple}9\color{green}0} \\
\hline
\cancel{\color{magenta}91} & \cancel{\color{red}92} & \cancel{\color{blue}93} & \cancel{\color{red}94} & \cancel{\color{green}95} & \cancel{\color{purple}96} & \bf97 & \cancel{\color{red}9\color{magenta}8} & \cancel{\color{blue}99} & \cancel{\color{red}10\color{green}0} \\
\hline
\end{array})]
[25]
위 표에서 빗금이 없는 수는 소수를 의미한다. 100이하의 소수는 모두 25개이며, 색깔을 입힌 것은 진행 과정을 알 수 있게 하기 위한 것이다.
물론 모든 소수를 찾는다면 사실상 이 방법 뿐이지만, 하나의 소수만을 찾는다면 이건 위에서 말한 [math(\sqrt n)] 나눗셈보다도 훨씬 느리니 당연히 꽝이다.

이산수학과 알고리즘이 발전하면서 소수 판정법은 비약적으로 발전했다. 1976년 발명된 밀러-라빈 판정법은 [math(\mathcal{O}(\log^3{n}))][26] 내에 소수를 판별할 수 있지만, 무작위 방법을 쓴다. 밀러-라빈 판정법의 원리는 간단히 말하자면 페르마의 소정리를 많은 경우에 만족시키는지 아닌지를 보는 것이다. 페르마의 소정리는 n이 소수일 때 만족하는 식을 주므로, 이 판정을 통과하지 못했다면 바로 n이 합성수임을 알 수 있다. 하지만 어떤 합성수 n이 여러 번의 판정을 우연히 통과할 확률은 시행횟수 k에 따라서 1/4k 이하로 현격하게 줄어드니(실제로는 이보다 더욱 작다), 이 확률을 무시한다면 실용적으로는 "k번 판정을 통과했으니 소수일 것이다"라고 할 수 있다. 물론 이 어떤 확률급의 확률에 재수없게 걸려 합성수를 소수라고 판별할 가능성도 있는데, 이 경우에는 별 도리가 없고 소수가 아니라고 예외적으로 하드코딩해야 한다.

2002년에 인도의 세 학생 Manindra Agrawal, Neeraj Kayal, Nitin Saxena이 결정론적 방법을 쓰는 AKS 알고리즘을 개발함으로써,결정론적인 소수판정이 이론적으로 [math(\mathcal{O}(\log^{12+o(1)}{n}))] 안에 풀릴 수 있음을, 즉 P-문제임을 보였다. P-NP 문제 참고. 2005년에는 [math(\mathcal{O}(\log^{6+o(1)}{n}))]인 결정론적 알고리즘이 나왔으나 실용적으로는 훨씬 빠른 밀러-라빈 등을 선호한다.
AKS 이 세명은 자신중 한명인 Manindra Agrawal 제기한 추측이 참이라면 밀러-라빈과 맞먹는 [math(\mathcal{O}(\log^{3+o(1)}{n}))]인 결정론적 알고리즘이 가능함을 보였다. 정수론 관련 추측답게 [math(10^{12})]까지 반례는 없으나 증명도 안되었다.

한편 소인수분해의 문제는 소수 판정과는 다르게 매우 어렵다. 확률적 해법으로 양보하더라도 [math(\log{n})]의 다항시간 등으로 나온다는 것은 아직 상상도 할 수 없다. 고전 컴퓨터가 아닌 양자컴퓨터의 경우는 이미 [math(\log^3{n})]인 쇼어알고리즘이 나와있으나 자리수가 늘어날수록 양자오류를 보정하는 작업이 만만치 않아 2001년 15를 소인수분해한 뒤 무려 11년이나 지나 21을 소인수분해 가능했다. 그리곤 감감무소식. 이 문제가 어려운게 어찌 보면 다행인데, 이 문제가 쉽다면 소수 기반 암호 체계의 대부분이 모두 무용지물이라서다.

자연수 n을 대입했을 때 n번째 소수가 튀어나오는 공식이 있기는 한데.. 윌런스의 공식 참조. 바닥함수와 간단한 곱셈을 이용한 공식도 있긴 한데, 카오스라 초항이 조금만 틀어져도 영 도움이 안된다. 사실 소수를 사용하는 법 말곤 초항을 계산할 방법조차 알려진 게 없으니 무쓸모.

참고로 소수 계량 함수 [math(\pi(x))]는 x보다 작거나 같은 소수가 몇 개인지에 대한 함수이다. 이 소수 계량 함수를 정확하게 만들어 내는 것은 불가능하지만, 그것이 대략 어떤 함수에 근사되는가를 연구하는 문제가 바로 소수 정리이다.[27] 그런데, 이걸 깊게 파면 튀어나오는 게 이 바닥의 최종 보스이다.

8. 여담

수와 연산
Numbers and Operations
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px" 		<colbgcolor=#765432> 수 체계 자연수 ( 수학적 귀납법 · 홀수 · 짝수 · 소수 · 합성수) · 정수 · 유리수 ( 정수가 아닌 유리수) · 실수 ( 무리수 · 초월수) · 복소수 ( 허수) · 사원수
표현 숫자 ( 아라비아 숫자 · 로마 숫자 · 그리스 숫자) · 기수법( 자연어 수 표기법 · 과학적 표기법 · E 표기법 · 커누스 윗화살표 표기법 · 콘웨이 연쇄 화살표 표기법 · BEAF · 버드 표기법) · 진법 ( 십진법 · 이진법 · 8진법 · 12진법 · 16진법 · 60진법) · 분수 ( 분모 · 분자 · 기약분수 · 번분수 · 연분수 · 통분 · 약분) · 소수 { 유한소수 · 무한소수 ( 순환소수 · 비순환소수)} · 환원 불능 · 미지수 · 변수 · 상수
연산 사칙연산 ( 덧셈 · 뺄셈 · 곱셈 구구단 · 나눗셈) · 역수 · 절댓값 · 제곱근 ( 이중근호) · 거듭제곱 · 로그 ( 상용로그 · 자연로그 · 이진로그) · 검산 · 연산자 · 교환자
방식 암산 · 세로셈법 · 주판 · 산가지 · 네이피어 계산봉 · 계산기 · 계산자
용어 이항연산( 표기법) · 항등원과 역원 · 교환법칙 · 결합법칙 · 분배법칙
기타 수에 관련된 사항 ( 0과 1 사이의 수 · 음수 · 작은 수 · 큰 수) · 혼합 계산 ( 48÷2(9+3) · 111+1×2=224 · 2+2×2) · 0으로 나누기( 바퀴 이론) · 0의 0제곱 }}}}}}}}}


[1] 자신과 더하면 0이 되는 수. [2] 꼭 자연수여야 한다. 왜냐하면 소수까지 취급해버리면 사실상 모든 수가 합성수가 되기 때문. 이는 나머지가 있는 나눗셈을 생각해보자. 자연수만 취급했을 때 나머지가 있으면 그 수는 나누어떨어지지 않는 셈이다. [3] 단, 1은 제외된다. 왜냐하면 소인수분해를 할 때 1도 소수면 무한히 많은 해결 방식이 있기 때문이다. 예를 들어 57을 소인수분해 할때 19×3, 19×3×1, 19×3×1²,···으로, 굳이 두자릿수일 필요도 없이 가장 작은 합성수인 4만 해도 이미 2×2, 2×2×1, 2×2×1²,···으로 소인수분해의 답이 무한하게 많아진다. 그래서 1은 소수도 합성수도 아닌 수로 지정했다. 참고로 1은 몇 번을 곱하든지에 상관없이 1이 되며, 양의 약수가 1개인 유일한 자연수이다. [4] 이는 환에서 소 아이디얼을 배우면 어떤 느낌인지 알 것이다. [5] 이는 소 아이디얼 역시 진 아이디얼(환 자기자신 제외)에서 다루는 것과 비슷하다. [6] 곱셈의 역수를 가진 원소 [7] 단, 2가 들어 있다면 매우 가끔 아래의 첫 번째 등식이 성립한다. 예를 들어, [math(2+3=5 \in \mathbb{P})]이다. 물론, 2가 들어 있더라도 항상은 아니다. [math(2+7=9 \notin \mathbb{P})]. 이 등식을 성립하게 만드는 소수들이 바로 그 유명한 쌍둥이 소수. [8] 이것을 증명하는 과정은 자연수의 무한성 증명보다는 약간 어렵지만 그래도 무려 소수의 무한성 증명보다도 훨씬 쉽다. 임의의 자연수 n에 대해서 (n+1)!+2, (n+1)!+3, (n+1)!+4, ..., (n+1)!+(n+1)은 모두 소수가 아니므로 소수가 없는 구간이 최소 n이 되도록 하는 소수 사막을 찾을 수 있다. 소수가 무한히 있는 만큼 무한히 길거나 유한하지만 모든 소수 사막 중에서 가장 긴 소수 사막은 없다. [9] 게다가 원주율처럼 그 어떤 규칙도 발견되지 않았다. 그리고 짝수라도 수가 크다고 해서 무조건 약수가 많은 게 아니듯 아주 큰 수에서도 연속으로 2번 이상의 소수가 발견될 수도 있다. 그리고 한 가지 더 보태자면, P(n)의 값은 1부터 n까지의 수들 가운데에 해당되는 소수의 개수라고 할 때, 함수의 결과값 상승률이 거의 0에 수렴하므로 n의 값이 많이 커져야 할 필요가 있다. [10] <제타 함수의 비밀>(구로카와 노부시게 지음)이라는 책에 이 증명이 나와 있다. [11] 해당 방법으로 만들어진 수가 소수가 아닌 가장 작은 경우는 2×3×5×7×11×13+1=30031=59×509이다. [12] 출처를 보면 알 수 있듯, 유클리드가 실제로 증명한건 주어진 소수열에서 새로운 소수를 찾는 방법에 가깝고 애초에 가정이고 뭐고 안들어 갔으니 귀류법조차 아니다. n개의 소수가 주어졌을 때 n+1개의 소수를 찾는 방법이라 보면 오히려 수학적 귀납법에 가깝다. [13] 현재 밝혀진 최댓값은 [math(\sqrt{11}-\sqrt{7})]으로 약 0.67087이다. [14] 물론 여기서도 리만 가설처럼 비전공자는 이해조차 어려운 문제도 있다. [15] 만약 학생이 “왜 약수에서는 수의 음양을 따지지 않느냐”고 질문할 경우, 음수는 빚, 양수는 돈에 비유해 설명하면 쉽게 이해한다. 예를 들어 -3을 3으로 나누는 것은 빚 3억원을 세 명이 나눠 부담하는 것에 비유할 수 있고, 3을 3으로 나누는 것은 돈 3억원을 셋이 나눠 갖는 것에 비유할 수 있다. 두 경우 모두에서 한 사람 앞에 돌아간 액수는 1억으로 똑같지만, 그것이 빚이냐(-1억원) 돈이냐(1억원)의 차이만 있을 뿐이다. 즉 수가 음수간 양수건 나눠지는(약분되는) 방식은 동일하며 그 몫의 음양이 다를 뿐이다. [16] 정규 교육 과정에서 덧셈이면 몰라도 나눗셈, 곱셈은 가르치지 않으나 일반적인 십진법의 계산법과 동일하다. n진법의 구구단을 외우지 않았으니 시간이 오래 걸리긴 하겠지만. 방법은 한국어 웹에는 잘 나타나지 않고 영어 웹에서 검색해보자. [17] 찻간, 횟수, 곳간, 툇간, 숫자, 셋방. [18] 영어로 소수를 일컫는 말인 prime number에서 prime이 으뜸이라는 의미가 있기 때문에 솟아오른 수라고 번역했다는 주장이다. 이럴 경우 '솟수'는 비통사적 합성어라고 할 수 있다. [19] 이쪽 언어에서 종종 혼동되는 것은 ‘정수’다. 소수점 이하가 없는 수를 나타내는 整数와 양수를 나타내는 正数가 せいすう로 발음이 같기 때문이다. 중국어에서도 각각 整数(zhěngshù), 正数(zhèngshù)로 성조만 다르다. [20] n이 합성수라면 [math(\sqrt n)] 이하의 소인수가 있다고 쉽게 알 수 있다. [21] 2가 아닌 2의 배수들은 무조건 2라는 약수를 가지기 때문에 소수가 될 수 없다. [22] 3이 아닌 3의 배수들은 무조건 3이라는 약수를 가지기 때문에 소수가 될 수 없다. [23] 5가 아닌 5의 배수들은 무조건 5라는 약수를 가지기 때문에 소수가 될 수 없다. [24] 7이 아닌 7의 배수들은 무조건 7이라는 약수를 가지기 때문에 소수가 될 수 없다. [25] 2와 3을 동시에 약수로 가지는 수는 보라색으로 표기 [26] 예를 들어보자. 만약 n이 1000이라면, 8k(k는 비례상수)의 시간 내에 소수를 판별해 낼 수 있다는 것이다. 자세한 내용은 Big-O를 참조. [27] 여기서 빠질 수 없는 관계의 함수가 다름아닌 로그함수(정확히는 그 역수의 원시함수인 [math(mathrm{li}(x))])이다. [28] 정확히 2^53-1이다. 53비트 이내에서 수를 처리하는 것 같다. [29] 마법사와 검은 고양이 위즈라는 일본 퀴즈 RPG에서 출제된 적이 있었다. 보기로 1. 홀수 / 2. 짝수 / 3. 둘 다 맞음 / 4. 둘 다 아님이 주어졌는데, 정답은 후술하지만 4. 여기에 왜 답이 2번이 아니냐면서 항의하는 유저들로 인해 잠시 화제가 되었다. [30] 병렬처리로 인해 결과를 저장하기 난해함과 더불어 공식 하나를 추가할때마다 픽셀수에 비례해 처리량이 올라가는 제약 때문에 간단한 공식으로 난수를 구현해야하는 특성에 기인한다

파일:CC-white.svg 이 문서의 내용 중 전체 또는 일부는
문서의 r148 판
, 3번 문단
에서 가져왔습니다. 이전 역사 보러 가기
파일:CC-white.svg 이 문서의 내용 중 전체 또는 일부는 다른 문서에서 가져왔습니다.
[ 펼치기 · 접기 ]
문서의 r148 판 ( 이전 역사)
문서의 r 판 ( 이전 역사)

분류