소수 판별기

n은 소수 <=> d(n) = 2; previousPrime(97) = 97; nextPrime(97) = 97; nextPrime(1000000) = 1000003

n

판정 대상인 자연수이고 2에서 1000000까지입니다. 아래쪽 경계는 물려받은 것이 아니라 정한 것입니다. 1의 이전 소수는 존재하지 않으므로 1을 받아들이는 페이지는 그 줄을 정직하게 채우지 못합니다. 1이 소수인지는 계산이 아니라 정의의 문제이고, 아래의 질문에서 답합니다

d(n)

양의 약수의 개수이고 결과의 첫 줄이며, 판정이 기대는 유일한 근거입니다. d(n) = 2라는 것은 이 수를 나누는 수가 꼭 둘이라는 뜻이고 그것이 소수의 정의입니다. 이 값은 공유 수론 루틴에서 오므로, 같은 입력에 대해 약수 페이지와 소인수분해 페이지가 보고하는 값과 같습니다

d(n) = 2

판정 그 자체를 등식으로 적은 것입니다. 근사가 아니라 필요충분조건입니다. 약수가 꼭 둘일 때 그 수는 소수이고, 소수이면 약수가 꼭 둘입니다. 97의 약수는 1과 97이므로 개수가 2이고 배지가 소수로 읽힙니다. 100의 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100으로 개수가 9이므로 배지가 합성수로 읽힙니다

previousPrime(n)

n보다 크지 않은 소수 가운데 가장 큰 것입니다. 위쪽 경계를 포함하므로 n이 소수일 때 답은 n 자신입니다. 100에서는 97, 25에서는 23, 97에서는 97입니다. 구간을 닫아 둔 이유는 그렇지 않을 경우 n이 이미 소수일 때 무엇을 인쇄할지 정해야 하는데, 결과 패널의 빈 줄은 사실이 아니라 실패로 읽히기 때문입니다

nextPrime(n)

n보다 작지 않은 소수 가운데 가장 작은 것이고 아래쪽 경계를 포함하는 규칙은 같습니다. 25에서는 29, 100에서는 101, 97에서는 97입니다. 이 값은 입력 범위를 나갈 수 있습니다. nextPrime(1000000)이 1000003이고 이는 페이지가 받는 어떤 수보다도 큰 소수인데, 범위 밖이라며 거부하지 않고 답으로 보고합니다

1e6 부근

입력 상한 근처의 풍경이고 위쪽에 별도의 판정이 필요한 이유입니다. 100만 근처의 소수는 999983과 1000003이라서, 1000000에서 시작하는 탐색은 한쪽으로 100만을 넘어가야 합니다. 약수 개수를 세는 루틴은 100만을 넘는 인자를 거부하고 예외를 던지므로, 이웃 탐색은 그런 제한이 없는 자체 판정을 씁니다. 둘이 겹치는 구간에서는 같은 답을 내야 하고, 예시의 소수 줄들이 바로 그것을 확인합니다

이미 마음에 둔 수 근처에서 소수를 고르고 싶을 때가 가장 실용적인 이유입니다. 해시 표의 칸 수는 흔히 소수로 잡는데, 소수를 법으로 쓰면 공약수를 공유하는 키들이 한곳에 몰리지 않고 흩어지기 때문입니다. 칸이 1000개인 표는 25의 배수를 모두 같은 몇 칸에 밀어 넣지만 997개인 표는 그렇지 않습니다. 암호에서도 같은 감각이 쓰이고, 거기서는 크고 서로 멀리 떨어진 소수로 열쇠를 만듭니다. 어떤 수가 소수인지 확인하는 일은 나누어떨어짐 질문도 빠르게 정리합니다. 제곱근까지의 소수 가운데 나누는 것이 하나도 없으면 그 위에도 없기 때문이고, 배지가 그것을 한 단계로 답합니다. 쌍둥이 소수, 이웃한 소수 사이의 간격, 어떤 수가 두 소수의 곱인지 같은 퍼즐도 이 판정 위에 서 있습니다. 질문이 인수 쪽으로 돌아가면 소인수분해 페이지가 수를 소수들의 곱으로 쪼개며, 어떤 수가 이 수를 나누는지가 궁금하면 약수 페이지가 목록을 보여 줍니다. 판정 대상이 소수가 아닌데 무엇으로 만들어졌는지 알고 싶다면 이 페이지의 약수 개수가 단서이지 완전한 답은 아닙니다. 이 소수 판별기가 필요한 순간에는 이 페이지가 판정과 근거와 이웃을 한 화면에 모아 줍니다.

1. 소수인 경우: 97

   1. 97의 약수를 시험합니다. 2도 3도 5도 7도 11도 나누지 못합니다
   2. 제곱근에서 멈춥니다. 10 × 10 = 100이 이미 97을 넘으므로 더 볼 것이 없습니다
   3. 약수는 1과 97뿐이므로 개수가 2이고 이 수는 소수입니다
   4. 이전 소수는 97 자신입니다. 97이 이미 소수이고 탐색이 경계를 포함하기 때문입니다
   5. 다음 소수도 같은 이유로 97입니다

   기본 입력이고 경계를 포함하는 규칙을 가장 깨끗하게 보여 주는 자리입니다. 두 이웃이 모두 자기 자신으로 돌아오는데, 처음 보면 두 줄이 아무 일도 하지 않은 것처럼 보입니다. 그렇지 않습니다. 97보다 크지 않은 소수 가운데 가장 큰 것이 97이고, 97보다 작지 않은 소수 가운데 가장 작은 것도 97입니다. 반대로 엄격한 부등호를 쓰면 이 페이지가 가장 확신하는 입력에서 정확히 그 두 줄이 빈칸이 됩니다. 이 경우는 페이지 안의 두 판정이 만나는 자리이기도 합니다. 약수 개수는 2라고 말하고 이웃 탐색은 97이 소수라고 말하는데, 둘은 서로 다른 코드로 거기에 이릅니다.

2. 합성수인 경우: 100

   1. 100은 짝수라서 2가 나누고, 끝이 00이라서 4, 5, 10, 20, 25, 50도 나눕니다
   2. 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100으로 아홉 개입니다
   3. 아홉은 둘보다 많으므로 배지는 소수가 아니라 합성수로 읽힙니다
   4. 100 이하에서 가장 큰 소수는 97이고, 100 이상에서 가장 작은 소수는 101입니다
   5. 두 이웃이 모두 한 걸음 바깥에 있고, 이것이 소수 사이의 틈 한가운데에 앉은 합성수의 모습입니다

   이웃 두 줄이 실제로 일하는 것을 보여 주는 경우입니다. 수가 합성수일 때 쓸모 있는 출력은 그 두 줄입니다. 이 수가 아니라면 어느 수인지가 독자가 다음에 묻는 질문이기 때문입니다. 97과 101이 가장 가까운 소수이고 100이 그 사이에 있습니다. 약수 개수 9도 눈여겨볼 만합니다. 홀수인데, 이는 수가 완전제곱수일 때만 일어나는 일이고 100은 10의 제곱입니다. 그래서 개수만 한 번 보아도 분해를 하기 전에 이 수의 모양에 대해 무언가를 알 수 있습니다.

3. 소수 바로 옆의 수: 25

   1. 25의 약수는 1, 5, 25로 세 개입니다. 5가 자기 자신과 짝을 이루기 때문입니다
   2. 셋은 둘보다 많으므로 25는 합성수입니다
   3. 25에서 아래로 내려갑니다. 24, 23이고 23이 소수이므로 이전 소수입니다
   4. 25에서 위로 올라갑니다. 26, 27, 28, 29이고 29가 소수이므로 다음 소수입니다
   5. 여기서 간격은 모두 여섯입니다. 23과 29가 25를 사이에 두고 있습니다

   완전제곱수라서 약수 개수가 홀수인 경우이고, 두 이웃이 눈에 띄게 다른 거리에 있는 경우이기도 합니다. 아래로 둘, 위로 넷입니다. 개수가 3이라는 사실은 왜 기준이 소인수 개수가 아니라 2여야 하는지도 보여 줍니다. 25의 소인수는 5 하나뿐이지만 25는 소수가 아니고, 약수 개수는 분해식을 들여다보지 않고도 그것을 잡아냅니다.

입력은 2에서 1000000까지의 자연수여야 합니다. 0과 1은 거부하는데, 1이 거부되는 이유는 0과 다릅니다. 1은 범위를 벗어난 수가 아니라 정의의 문제이고, 1의 이전 소수는 존재하지 않습니다. 음수도 거부합니다. 소수성은 1보다 큰 자연수의 성질이고, 수학의 일부 갈래에는 음수 소수의 관례가 있지만 이 페이지는 그것을 채택하지 않습니다. 소수점이 있는 입력은 반올림하지 않고 거부합니다. 100만이라는 상한은 입력에만 걸립니다. 이웃 두 줄은 그 밖의 소수를 정당하게 보고할 수 있고, 100만 다음의 소수인 1000003은 거부되지 않고 그대로 보고됩니다. 판정 뒤에 있는 방법은 제곱근까지의 시험 나눗셈이고, 이 크기에서는 순식간이지만 스무 자리 수에서는 희망이 없습니다. 그 경계는 이 구현이 아니라 문제 자체의 성질입니다. 이 페이지는 수 세 개와 배지 하나를 보고합니다. 약수를 직접 나열하지 않고, 합성수를 분해하지 않으며, 범위가 아니라 한 번에 한 수만 판정합니다. 아래 참고표들은 입력을 따라가지 않고 고정된 줄을 보여 줍니다. 마지막으로 소수는 자기 자신을 이전 소수이자 다음 소수로 보고하는데, 이는 경계를 포함하는 구간을 고른 결과이지 아무것도 찾지 못한 두 줄이 아닙니다.

1은 소수인가요?

아닙니다. 합성수도 아닙니다. 소수는 1보다 크면서 양의 약수가 꼭 둘인 자연수로 정의되고, 1은 약수가 하나뿐이라 두 조건 모두에서 어긋납니다. 이것은 빠뜨린 것이 아니라 일부러 정한 것입니다. 1을 소수로 세면 모든 수의 소인수분해가 꼭 하나라는 정리가 성립하지 않게 됩니다. 분해식에 1을 원하는 만큼 곱할 수 있기 때문입니다. 1을 제외하는 것이 그 정리를 깨끗하게 지켜 줍니다. 산술이 아니라 정의의 문제이므로 이 페이지는 1을 입력으로 받지 않고, 답은 이 질문 자리에 있습니다.

이전 소수와 다음 소수가 왜 자기 자신으로 돌아오나요?

두 탐색 모두 경계를 포함하기 때문입니다. 이전 소수는 내 수보다 크지 않은 소수 가운데 가장 큰 것이고, 다음 소수는 내 수보다 작지 않은 소수 가운데 가장 작은 것입니다. 수가 이미 소수라면 두 설명에 모두 해당하므로 두 줄이 그 수를 보고합니다. 반대로 엄격한 부등호를 쓰면 소수를 넣었을 때 두 줄에 인쇄할 것이 남지 않습니다. 결과 패널의 빈 줄은 뭔가 잘못된 것으로 읽히고, 페이지는 자기가 가장 확신하는 경우에 답을 못 하게 됩니다. 이미 목표 자릿수에 있는 수가 그대로 돌아오는 반올림에서도 같은 관례를 씁니다.

입력은 100만을 못 넘는데 다음 소수는 왜 100만을 넘을 수 있나요?

상한은 물어볼 수 있는 것에 걸린 제한이지 답이 놓일 수 있는 범위가 아니기 때문입니다. 1000000 다음의 소수는 1000003이고, 이것을 인쇄하지 않는다는 것은 페이지가 받아들인 입력에 대한 지극히 정당한 질문을 거부한다는 뜻이 됩니다. 그래서 이웃 탐색은 상한이 없는 자체 판정으로 돌고, 약수 개수는 범위를 덮는 공유 루틴을 그대로 씁니다. 그래서 어떤 수가 소수인지를 두 가지 논리가 판단하게 되는데, 하나는 범위가 있고 하나는 없으며, 둘은 겹치는 구간에서 같은 답을 내야 합니다. 97 예시가 바로 그것을 확인합니다. 약수 개수는 2라고 말하고 이웃 탐색은 97이 소수라고 말합니다.

소수는 실제로 어디에 쓰나요?

주로 크기를 정할 때 씁니다. 해시 표에는 흔히 소수 개의 칸을 주는데, 소수를 법으로 쓰면 공약수를 공유하는 키들이 흩어지기 때문입니다. 칸이 1000개인 표는 25의 배수를 모두 같은 몇 자리에 보내지만 997개인 표는 그렇지 않습니다. 카운터가 한 바퀴 돌아 제자리로 오는 모든 곳에서도 같은 논리가 통합니다. 주기가 소수이면 데이터의 규칙적인 무늬와 공명하지 않습니다. 암호도 큰 축이고, 거기서는 아주 크고 서로 멀리 떨어진 소수로 열쇠를 만들며, 그 곱을 다시 두 소수로 되돌리기 어렵다는 점 위에 안전성이 서 있습니다. 작은 쓰임은 어디에나 있습니다. 나누어떨어짐 주장을 확인하는 일, 어떤 수가 두 소수의 곱인지 시험하는 일, 그리고 쌍둥이 소수와 이웃한 소수 사이의 간격에 관한 고전적인 퍼즐입니다.

어떻게 판정하고, 얼마나 확실한가요?

약수를 세어서 판정하고, 이는 확률적이 아니라 정확합니다. 어떤 수는 양의 약수가 꼭 둘일 때, 그리고 그럴 때만 소수이므로 그 개수가 틀릴 여지 없이 질문을 정리합니다. 속을 수도 있는 판정을 믿을 필요도 없습니다. 세는 일은 제곱근까지의 시험 나눗셈으로 하고, 100만이 상한인 것도 그 이상에서는 방법이 믿을 수 없어져서가 아니라 느려져서입니다. 훨씬 큰 수에서는 정확한 방법이 정말로 쓸 수 없어 확률적인 판정을 대신 쓰지만, 이 크기에서는 확실성보다 못한 것을 받아들일 이유가 없고 이 페이지는 받아들이지 않습니다.

판정만 보여 주지 않고 약수 개수도 보여 주는 이유는 무엇인가요?

개수가 판정의 이유이고, 그것을 함께 보여 주면 둘이 어긋날 수 없기 때문입니다. 배지는 두 번째 계산이 아니라 바로 옆에 인쇄된 수를 읽은 것입니다. 개수는 그 자체로도 쓸모가 있습니다. 홀수인 개수는 그 수가 완전제곱수라는 뜻이고, 제곱근이 다른 약수가 아니라 자기 자신과 짝을 이루기 때문입니다. 개수가 2라는 것은 소수의 정의입니다. 수의 크기에 비해 개수가 많으면 작은 인수를 많이 가진 수이고, 약수를 빠르게 모으는 종류입니다. 그리고 이 페이지를 다른 페이지와 이어 줍니다. 소인수분해 페이지는 같은 입력에 대해 같은 약수 개수를 지수에서 계산해 보고하므로, 두 페이지가 서로를 확인해 줍니다.

• Prime Number — 정의, 약수 개수로 하는 판정, 그리고 그 판정이 1을 제외하는 이유 — Wolfram MathWorld (United States)
• Prime Gaps — 이웃한 소수 사이의 거리, 그리고 100만 근처의 풍경이 어떻게 생겼는지 — Wolfram MathWorld (United States)
• Composite Number — 소수의 여집합, 그리고 1이 어느 쪽에도 속하지 않는 이유 — Wolfram MathWorld (United States)
• 教育部关于印发义务教育课程方案和课程标准(2022年版)的通知 — 이 통지의 첨부 목록 제5항이 《义务教育数学课程标准(2022年版)》에 해당하며, 소수와 합성수는 이 교육과정의 수와 대수 영역 내용이므로 원문과 학년군 요구는 이 첨부를 기준으로 합니다 — 中华人民共和国教育部