numbers 소수 목록 및 판별 도구 star

작동 방식

이 도구는 서로 다른 질문에 맞는 두 가지 알고리즘을 전환하며 사용합니다. 목록 모드는 에라토스테네스의 체를 이용해 특정 한계까지의 모든 소수를 찾습니다. 이는 지금도 일상적으로 쓰이는 가장 오래된 알고리즘 중 하나입니다(기원전 3세기 그리스 수학자 에라토스테네스가 고안한 것으로 전해집니다). 2부터 시작해 2의 모든 배수를 합성수로 표시하고, 다음으로 표시되지 않은 수(3)로 넘어가 그 배수를 모두 표시하고, 다음으로 표시되지 않은 수(5)로 넘어가는 식으로 반복합니다. 한계값의 제곱근에 도달했을 때 표시되지 않고 남아 있는 수가 소수입니다. 작은 예를 들면: 30까지 체로 거를 때, 먼저 2의 배수(4, 6, 8, …)를 지우고, 다음으로 3의 배수(6, 9, 12, … 일부는 이미 지워짐)를 지우고, 그다음 5의 배수(10, 15, …)를 지웁니다 — 5×5=25는 30 이하이지만 7×7=49는 30을 넘으므로 여기서 멈출 수 있으며, 남는 수인 2, 3, 5, 7, 11, 13, 17, 19, 23, 29가 전체 목록입니다. 이 과정은 O(n log log n) 시간에 실행되므로, 범위가 수십만까지 커져도 빠른 속도를 유지합니다.

확인 모드는 다른 질문 — 이 특정 숫자 하나가 소수인가? — 에 답하며, 제곱근까지의 시험 나눗셈을 사용합니다. n이 소수인지 확인하려면 2부터 √n까지의 약수만 확인하면 충분합니다. 그 이유는 다음과 같습니다: 만약 n = a × b이고 a와 b가 모두 √n보다 크다면, a × b는 n보다 커지게 되어 모순이 발생합니다. 따라서 두 인수 중 적어도 하나는 √n 이하여야 하며, 반복문이 끝나기 전에 그 값이 발견됩니다. 예시: 97을 확인하려면 2, 3, 5, 7로만 나누어보면 됩니다(9² = 81은 97 이하이지만 10² = 100은 97을 넘기 때문입니다) — 어느 것도 나누어떨어지지 않으므로 97은 소수입니다.

알아두어야 할 점

이 두 모드가 존재하는 이유는 서로 다른 방식으로 트레이드오프를 하기 때문입니다: 체는 한 번에 많은 소수를 생성하는 데 효율적이지만, 거대한 한계값 근처의 숫자 하나에만 관심이 있다면 메모리와 시간을 낭비하게 됩니다. 반대로 시험 나눗셈은 한 번의 확인에는 효율적이지만, 넓은 범위의 모든 숫자에 대해 하나씩 반복하면 지나치게 느립니다. 작업에 맞는 방식을 고르는 것, 바로 그것이 이 도구가 두 모드를 모두 제공하는 이유입니다.

• 1은 정의와 관례에 따라 소수에서 제외됩니다 — 약수가 하나뿐이며 둘이 아니기 때문인데, 만약 포함된다면 소인수분해의 유일성이 깨질 것입니다.
• 2는 유일한 짝수 소수입니다. 다른 모든 짝수는 2로 나누어떨어지므로 합성수입니다.
• 숫자가 커질수록 소수는 평균적으로 희소해지지만 결코 나타나기를 멈추지 않습니다 — 유클리드는 2천 년도 더 전에 소수가 무한히 많다는 사실을 증명했습니다.