소수 판별기

소수란? 언제 확인하나

소수(prime number)는 1과 자기 자신으로만 나누어떨어지는, 1보다 큰 자연수입니다. 7은 1과 7로만 나누어떨어지므로 소수이고, 8은 1, 2, 4, 8로 나누어떨어지므로 소수가 아닙니다. 1보다 큰 자연수 중 소수가 아닌 수는 합성수라고 부릅니다. 수학 숙제의 약수·배수 문제, 암호·해시 값 설계를 위한 소수 선택, 달력·주기 퍼즐, 프로그래밍 연습(소수 판별 알고리즘)에서 자주 필요합니다. 이 도구는 한 숫자의 소수 여부와 합성수일 때의 소인수분해를 알려 주고, 10,000 이하의 소수 목록을 만들어 줍니다.

판별 원리: 제곱근까지만 나눠 본다

n이 합성수라면 n = a × b (1 < a ≤ b)로 쓸 수 있고, a가 b보다 크지 않으므로 a² ≤ n, 즉 a ≤ √n입니다. 따라서 n이 합성수라면 √n 이하에 반드시 1이 아닌 약수가 하나 있고, 2부터 √n까지 나눠 보아 나누어떨어지는 수가 없으면 소수라고 결론 낼 수 있습니다. 이 도구는 여기서 더 줄여 2를 먼저 처리한 뒤 3, 5, 7, … 홀수로만 나눕니다. 짝수는 이미 2로 걸러졌기 때문입니다.

소수 판별: 2 ≤ d ≤ √n 인 d 중 n의 약수가 없으면 소수

목록 생성은 같은 원리로 각 수를 판별합니다. 수가 아주 커지면 에라토스테네스의 체(작은 소수의 배수를 차례로 지우는 방법)가 훨씬 빠르며, 이 페이지의 아래 표는 빌드 시 그 방식으로 100만까지 계산한 값입니다.

100 미만의 소수 25개

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

1,000 이하의 소수 사이에는 차이가 2인 쌍둥이 소수가 35쌍 있습니다(3,5 / 5,7 / 11,13 …). 5와 7처럼 붙어 있는 쌍도 있고, 소수 사이 간격이 커지는 구간도 있습니다. 아래는 간격이 처음으로 6, 8, 14 이상이 되는 지점입니다.

소수는 얼마나 있나: π(x) 참고표

x 이하의 소수 개수를 π(x)라 합니다. 소수 정리에 따르면 x가 클수록 π(x)는 x/ln x에 가까워집니다. 아래는 실제 개수와 어림값의 비교입니다.

10,000까지의 소수가 1,229개이므로 이 도구의 목록 기능이 보여 주는 최대 개수가 1,229개입니다. 소수는 커질수록 드물어지지만 끝없이 이어집니다(유클리드가 증명).

검산된 예시

예시 1. 97. √97 ≈ 9.85이므로 3, 5, 7, 9만 나눠 봅니다. 모두 나누어떨어지지 않으므로 97은 소수입니다.

예시 2. 91. 흔히 소수로 착각하는 수입니다. 3, 5로는 안 나뉘지만 7로 나누면 13이 되어 7 × 13입니다. 7×13의 곱이라 합성수입니다.

예시 3. 360의 소인수분해. 2^3 × 3^2 × 5. 합성수는 소수의 곱으로 유일하게 나타낼 수 있다는 산술의 기본 정리를 확인하는 예입니다.

예시 4. 2³¹ − 1 = 2,147,483,647. 메르센 수라 불리는 이 수는 소수입니다. 판별에는 √n ≈ 46,340까지 홀수 23,169개만 나눠 보면 됩니다. 20억이 넘는 수도 2만여 번의 나눗셈으로 판정되는 셈입니다.

수가 커질 때 나눗셈 횟수는 얼마나 늘까

나눗셈으로 판별하는 방법은 구조가 단순한 대신, 입력이 소수일 때 √n까지의 홀수를 모두 나눠 봐야 끝납니다. 즉 최악의 횟수는 약 √n÷2이고, 수가 100배 커지면 횟수는 10배 커집니다. 아래 표는 3부터 ⌊√n⌋까지의 홀수 개수를 빌드 시 계산한 값입니다. 이 도구가 받는 최대값인 1,000조(10^15) 근처의 소수는 약 1,581만 번까지 나눠 보게 되므로 브라우저에서 잠시 멈춘 듯 보일 수 있습니다. 합성수는 작은 약수에서 바로 끝나므로 훨씬 빨리 답이 나옵니다.

소수의 끝자리는 어떻게 분포하나

2와 5를 제외하면 소수의 끝자리는 1, 3, 7, 9 중 하나입니다. 10과 서로소인 자리이기 때문입니다. 100만 이하의 소수 78,498개를 끝자리별로 센 결과는 아래와 같고, 네 자리가 거의 비슷한 비율을 차지합니다. 그렇다고 끝자리가 1, 3, 7, 9라는 사실이 소수의 증거는 아니며, 소수 후보를 추릴 때 5의 배수와 짝수를 먼저 빼는 용도로만 씁니다.

소인수분해와 약수의 개수

합성수의 약수 개수는 소인수분해의 지수에 1을 더해 곱하면 구해집니다. 소수는 약수가 정확히 2개(1과 자기 자신)이므로 약수 개수가 2인 수가 곧 소수라는 말과 같습니다. 아래 표는 약수 개수를 직접 세어 확인한 값으로, 약수가 많은 수일수록 똑같이 나누기 쉽습니다.

계산기 없이 합성수를 알아보는 요령

도구에 넣기 전에 눈으로 합성수를 걸러내는 방법이 몇 가지 있습니다. 첫째, 끝자리가 0, 2, 4, 5, 6, 8이면 2 또는 5로 나뉩니다(2와 5 자체는 예외). 둘째, 각 자리 숫자를 더한 합이 3의 배수이면 3으로 나뉩니다. 573은 5+7+3=15가 3의 배수이므로 소수가 아닙니다. 셋째, 11은 홀수 자리 숫자의 합과 짝수 자리 숫자의 합의 차이가 0이거나 11의 배수일 때 나뉩니다. 143은 1−4+3=0이므로 11로 나뉘고 11×13입니다. 넷째, 7과 13은 간단한 규칙이 없으므로 1001 = 7×11×13이라는 사실을 기억해 두면 편합니다. 이 규칙으로 걸러내지 못한 수가 앞에서 나눠 보는 대상이 됩니다.

자주 틀리는 합성수는 7×17 = 119, 11×13 = 143, 13×17 = 221처럼 2, 3, 5로는 나뉘지 않고 두 번째로 작은 소수들의 곱인 경우입니다. 이 수들은 끝자리나 3의 배수 판정만으로 소수라고 단정하기 쉽습니다. 1729 = 7×13×19처럼 3개의 소수를 곱한 수도 같은 이유로 소수처럼 보일 수 있으니, 의심되면 도구로 확인하세요.

생활과 코딩에서 소수가 쓰이는 장면

조 편성. 학급 인원이 29명처럼 소수이면 똑같은 크기의 조를 만들 방법이 1명씩 29조 또는 한 조뿐입니다. 30명은 약수가 8개(1, 2, 3, 5, 6, 10, 15, 30)라 2, 3, 5, 6명 조로 모두 나눌 수 있습니다. 행사 인원을 정할 때 약수가 많은 수를 고르면 조 편성이 쉬워집니다.

톱니바퀴의 맞물림. 이빨이 12개와 18개인 톱니바퀴는 최소공배수 36 때문에 36칸마다 같은 이빨끼리 다시 만나 마모가 한쪽에 몰립니다. 13개와 18개처럼 서로소를 쓰면 최소공배수가 234라서 같은 이빨 쌍이 다시 만나기까지 훨씬 오래 걸려 마모가 고르게 퍼집니다. 이빨 수에 소수나 서로소 조합을 쓰는 이유입니다.

해시 테이블의 크기. 100의 배수로만 이루어진 키 1,000개를 크기 1,000인 테이블에 나머지 연산으로 넣으면 10칸만 쓰여 충돌이 폭발합니다. 크기를 소수 997로 하면 100과 997이 서로소라서 서로 다른 997칸이 모두 쓰입니다. 키에 일정한 약수 패턴이 있어도 소수 크기는 그 패턴이 나머지에 반영되지 않게 해 줍니다. 위 숫자는 직접 계산해 확인한 값입니다.

흔한 오해와 한계

• 1은 소수가 아닙니다. 정의가 "1보다 큰 자연수"이기 때문입니다. 1을 소수로 두면 소인수분해가 유일하지 않게 됩니다(6 = 2×3 = 1×2×3…).
• 2는 유일한 짝수 소수입니다. 나머지 짝수는 모두 2로 나뉘는 합성수입니다.
• 끝자리나 3의 배수만 보고 판단하지 마세요. 끝이 1, 3, 7, 9로 끝나도 합성수일 수 있습니다(91, 119, 143 등).
• 소수는 홀수만 있는 것이 아닙니다. 2가 있어서 "소수는 홀수"라는 말은 틀립니다.
• 매우 큰 수에는 한계가 있습니다. 이 도구는 브라우저가 정확히 다룰 수 있는 정수(약 9천조 이하) 범위에서 나눗셈으로 판별하며, 수백 자리 소수 판정이나 RSA급 소수 생성은 다루지 않습니다.
• 소수 목록은 10,000까지입니다. 더 큰 범위는 처리 속도를 위해 제한합니다.

결과를 어떻게 활용하나

합성수라는 결과가 나오면 도구가 보여 주는 소인수분해를 이용해 약수의 개수(지수에 1을 더해 곱함), 최대공약수·최소공배수 등을 구할 수 있습니다. 예를 들어 360 = 2³×3²×5의 약수 개수는 (3+1)(2+1)(1+1) = 24개입니다. 프로그래밍에서는 해시 테이블 크기나 난수 생성기의 모듈러스에 소수를 쓰는 이유(나머지 패턴이 덜 반복됨)를 이해하는 데 도움이 됩니다. 암호 분야에서 소수는 두 큰 소수의 곱을 소인수분해하기 어렵다는 점을 이용한 RSA의 바탕이 되지만, 실제 암호용 소수는 이 도구의 범위를 훨씬 넘는 크기이므로 이 도구로 키를 만들 수는 없습니다.

자주 묻는 질문

관련 도구

• 최대공약수·최소공배수 계산기
• 순열·조합 계산기
• 마방진 생성기
• 진법 변환기