소수 판별기（무료）— 최대 1,000자리·소인수분해까지

최대 1,000자리 숫자가 소수인지 즉시 판별합니다. 소인수분해, 이전·다음 소수, 시험 나눗셈 과정, 그리고 어떤 판정법으로 확정했는지까지 보여주는 무료 도구입니다.

마지막 업데이트: 2026-09-03

1,000 미만의 소수 전체 목록（168개）

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	101	103	107	109	113	127	131	137	139	149	151
157	163	167	173	179	181	191	193	197	199	211	223
227	229	233	239	241	251	257	263	269	271	277	281
283	293	307	311	313	317	331	337	347	349	353	359
367	373	379	383	389	397	401	409	419	421	431	433
439	443	449	457	461	463	467	479	487	491	499	503
509	521	523	541	547	557	563	569	571	577	587	593
599	601	607	613	617	619	631	641	643	647	653	659
661	673	677	683	691	701	709	719	727	733	739	743
751	757	761	769	773	787	797	809	811	821	823	827
829	839	853	857	859	863	877	881	883	887	907	911
919	929	937	941	947	953	967	971	977	983	991	997

1,000 미만의 나머지 수는 모두 합성수로, 1과 자기 자신 이외의 약수를 적어도 하나 가지고 있습니다.

10의 거듭제곱마다 소수는 몇 개일까요?

이하의 범위	소수의 개수 π(x)	소수의 비율
10	4	40%
100	25	25%
1,000	168	16.8%
10⁴	1,229	12.29%
10⁵	9,592	9.59%
10⁶	78,498	7.85%
10⁷	664,579	6.65%
10⁸	5,761,455	5.76%
10⁹	50,847,534	5.08%
10¹⁰	455,052,511	4.55%
10¹²	37,607,912,018	3.76%
10¹⁵	29,844,570,422,669	2.98%

π(x)는 소수 계량 함수로, x 이하의 소수 개수를 나타냅니다. 비율은 점점 작아지지만（x 근방에서는 대략 ln(x)개 중 1개가 소수）, 결코 0이 되지는 않습니다. 소수는 무한히 존재하기 때문입니다.

소수 판별기란

소수 판별기는 입력한 정수가 「1과 자기 자신 외에는 약수를 갖지 않는 수」인지 확인하는 도구입니다. 작은 수라면 손으로 시험 나눗셈을 해서 확인할 수 있지만, 암호 키 후보나 수학 경시대회 문제, 수백 자리에 이르는 수라면 시험 나눗셈만으로는 현실적인 시간 안에 끝나지 않습니다. 그래서 숫자의 규모에 따라 다른 판정법을 사용해야 합니다.

이 도구는 최대 1,000자리까지의 정수를 지원하며, 숫자의 크기에 따라 가장 빠르면서도 수학적으로 신뢰할 수 있는 판정법을 자동으로 선택합니다. 작은 수는 시험 나눗셈, 약 3.3×10²⁴ 미만은 밀러–라빈 검사에 의한 결정적 증명, 그보다 큰 수는 베일리–PSW 검사에 의한 확률적 소수 판정을 사용합니다. 소인수분해와 이전·다음 소수, 어떤 방법으로 결론이 나왔는지도 함께 표시됩니다.

소수 판별 사용법

정수를 입력합니다 입력란에 최대 1,000자리까지의 정수를 입력하거나 붙여넣습니다. 쉼표와 공백은 자동으로 무시됩니다.
판별 결과를 확인합니다 소수, 합성수, 특수한 경우인 1 중 하나가 표시되며, 어떤 판정법으로 결론을 냈는지도 함께 나타납니다.
자세한 정보를 확인합니다 소인수분해, 이전·다음 소수, 쌍둥이 소수나 메르센 소수 같은 성질을 확인할 수 있습니다.
시험 나눗셈 과정을 따라갑니다 비교적 작은 수라면 실제로 어떤 나눗수까지 시도했는지 표로 확인할 수 있습니다.

더 잘 활용하기 위한 팁

소수란 1보다 큰 정수 중에서 1과 자기 자신 이외에 약수가 없는 수입니다. 2, 3, 5, 7, 11, 13, … 으로 이어지며 이 수열은 끝나지 않습니다.
가장 기본적인 소수 판별법은 시험 나눗셈법입니다. 2부터 √N까지의 정수로 차례로 나누어 봅니다. √N에서 멈춰도 되는 이유는 N = a × b로 쓸 수 있다면 두 인수 중 작은 쪽은 반드시 √N 이하가 되기 때문입니다.
손으로 계산해도 많은 수는 금방 걸러낼 수 있습니다. 2를 제외한 짝수, 끝자리가 5인 수, 각 자리 숫자의 합이 3의 배수인 수는 모두 합성수입니다. 또한 3보다 큰 소수는 반드시 6k − 1 또는 6k + 1의 형태입니다.
큰 수에서는 시험 나눗셈법이 현실적이지 않으므로 컴퓨터는 밀러-라빈 판정법과 Baillie–PSW 판정법을 사용합니다. 이 페이지도 두 방법을 구현했기 때문에 최대 1,000자리 수를 붙여 넣어도 1초 이내에 판별할 수 있습니다.
1은 소수가 아닙니다（정의에 "1보다 큰"이라는 조건이 있습니다）. 또한 2는 유일한 짝수 소수입니다. 그보다 큰 짝수는 모두 2로 나누어지기 때문입니다.

활용 사례

숙제나 경시대회 답 검산

증명 문제나 연습 문제에서 소수라고 판단한 수가 정말 맞는지 바로 확인할 수 있습니다. 틀렸다면 소인수분해도 함께 표시됩니다.

암호 기술의 원리 체험

큰 후보 수를 입력해 RSA 암호 등에서 쓰이는 소수 판정의 개념을, 시험 나눗셈과 밀러–라빈／베일리–PSW 검사의 차이로 체감할 수 있습니다.

숫자의 특별한 성질 확인

쌍둥이 소수, 소피 제르맹 소수, 메르센 소수, 페르마 소수에 해당하는지 자료를 찾아보지 않고도 그 자리에서 확인할 수 있습니다.

프로그래밍 학습과 알고리즘 이해

시험 나눗셈 단계표를 보면서 소수 판정 알고리즘이 어떻게 결론을 내리는지, 직접 구현하기 전에 이해할 수 있습니다.

용어 설명

소수: 1보다 큰 정수 중 1과 자기 자신 외에는 약수를 갖지 않는 수입니다. 2, 3, 5, 7, 11, 13, … 처럼 끝없이 이어집니다.
합성수: 1과 자기 자신 외에도 다른 약수를 가진 정수입니다. 소수들의 곱으로 나타낼 수 있습니다.
시험 나눗셈법: 2부터 √N까지의 정수로 차례로 나누어 보는 판정법입니다. 완전한 증명이지만 N이 크면 현실적인 시간 안에 끝나지 않습니다.
밀러–라빈 검사: N을 법으로 한 1의 제곱근의 성질을 이용하는 판정법입니다. 충분히 많은 밑을 사용하면 약 3.3×10²⁴ 미만의 수에 대해 결정적인 증명이 됩니다.
베일리–PSW 검사: 밀러–라빈 검사와 강한 루카스 검사를 결합한 판정법입니다. 결정적 증명이 불가능할 만큼 큰 수에 사용되며, 지금까지 반례는 발견되지 않았습니다.
확률적 소수: 베일리–PSW처럼 강력한 판정법을 통과한 수를 말합니다. 소수일 가능성이 매우 높지만 수학적으로 완전한 증명은 아닙니다.
쌍둥이 소수: 11과 13처럼 차이가 정확히 2인 소수 쌍입니다. 무한히 존재하는지는 아직 풀리지 않은 수학 난제입니다.
메르센 소수: 2의 p제곱에서 1을 뺀 형태의 소수입니다. 지금까지 발견된 최대급 소수 중 다수가 이 형태입니다.

자주 묻는 질문

1,000자리까지 지원합니다. 10¹² 미만은 시험 나눗셈법, 3,317,044,064,679,887,385,961,981 미만은 결정적인 밀러-라빈 판정법, 그보다 큰 수는 Baillie–PSW 판정법으로 판별합니다. 소인수분해와 앞뒤 소수 탐색은 소수 판별보다 계산량이 훨씬 크기 때문에 지원 범위가 이보다 좁습니다.

약 3.3 × 10²⁴을 넘는 수의 결과는 Baillie–PSW 판정법에 따른 것으로, 반례는 하나도 발견되지 않았지만 증명도 없습니다. 실제로 암호 라이브러리가 의존하는 판정법이기도 하므로 "확률적 소수"라는 결과는 매우 신뢰할 수 있습니다. 반대 방향의 판정에는 모호함이 없습니다. 합성수로 표시된 경우에는 증거나 약수가 실제로 발견된 것이므로 그것은 증명입니다.

소수의 정의가 "1보다 큰 정수"이기 때문입니다. 1을 제외해야 소인수분해의 유일성이 유지됩니다. 만약 1을 소수에 포함하면 6은 2 × 3으로도, 1 × 2 × 3으로도, 1 × 1 × 2 × 3으로도 끝없이 쓸 수 있게 되어 산술의 기본정리가 성립하지 않습니다.

2는 1과 자기 자신 이외에 약수가 없으므로 정의를 만족합니다. 또한 유일한 짝수 소수입니다. 2보다 큰 짝수는 모두 2로 나누어지므로 세 번째 약수를 갖게 되기 때문입니다.

존재하지 않습니다. 기원전 300년경 유클리드가 소수의 무한성을 증명했습니다. 유한한 개수의 소수를 모두 곱한 뒤 1을 더하면, 그 수는 목록에 없는 소인수를 갖기 때문입니다. 존재하는 것은 "현재 알려진 가장 큰 소수"뿐이며 그 기록은 계속 갱신되고 있습니다. 현재는 2024년에 발견된 2¹³⁶²⁷⁹⁸⁴¹ − 1입니다.

제곱근 이하의 소수（2, 3, 5, 7, 11, …）로 차례로 나누어 보세요. 391이라면 √391 ≈ 19.8이므로 2, 3, 5, 7, 11, 13, 17, 19만 확인하면 충분하고, 17로 나누어져 391 = 17 × 23임을 알 수 있습니다. 각 자리 숫자의 합이 3의 배수면 3으로 나누어진다는 판정법도 유용합니다.

여담 ― 소수는 왜 중요한가

소수는 흔히 "수의 원자"라고 불립니다. 산술의 기본정리에 따르면 1보다 큰 모든 정수는 소수의 곱으로 오직 한 가지 방법으로만 나타낼 수 있습니다. 즉 소수는 모든 정수를 조립하기 위한, 더 이상 쪼갤 수 없는 부품인 셈입니다. 위에 표시되는 소인수분해가 유일한 이유도 여기에 있으며, 360은 2³ × 3² × 5이고 그 밖의 표현 방법은 없습니다.

거대한 수가 소수인지 "판별하는" 것과 그것을 "소인수분해하는" 것은 서로 다른 문제이며, 그 차이의 역사는 알아둘 만합니다. 페르마의 소정리를 쓰면 빠른 판별이 가능하지만, 어떤 밑을 사용해도 통과해 버리는 합성수가 존재합니다. 그중 가장 작은 예가 561이며 위의 버튼으로 확인해 볼 수 있습니다（이런 수를 카마이클 수라고 합니다）. 밀러-라빈 판정법은 도중에 1의 제곱근을 확인함으로써 이 빈틈을 막았고, 처음 13개의 소수를 밑으로 사용하면 약 3.3 × 10²⁴ 미만의 모든 수에 대해 결정적인 판정법이 됨이 증명되어 있습니다. 그 범위를 넘어서면 이 페이지는 강한 뤼카 판정법을 더한 Baillie–PSW 판정법을 사용합니다. 이 판정을 통과하는 합성수는 아직 하나도 발견되지 않았지만 증명은 없기 때문에, 매우 큰 수의 결과는 "확률적 소수"로 표시합니다.

이처럼 "판별은 쉬운데 분해는 어렵다"는 비대칭성이 현대 암호 기술을 떠받치고 있습니다. HTTPS 통신과 전자서명을 지금도 지켜 주는 RSA 암호는 큰 소수 두 개를 곱해서 공개키를 만듭니다. 그 곱에서 원래의 소수를 되찾는 일은 사실상 불가능하다고 여겨지기 때문에, 검증은 순식간에 끝나지만 분해는 할 수 없는 상태를 만들 수 있는 것입니다. 이 페이지에서도 그 차이를 체감할 수 있습니다. 1,000자리 수의 소수 판별은 거의 즉시 끝나지만, 30자리 소수 두 개를 곱한 60자리 합성수는 소인수분해를 끝내지 못합니다.

소수에는 수학에서 가장 오래된 미해결 문제도 남아 있습니다. 11과 13, 또는 1,000,000,000,061과 1,000,000,000,063 같은 쌍둥이 소수가 무한히 존재하는지는 아직 아무도 모릅니다. 소수 자체가 무한하다는 사실은 기원전 300년경 유클리드가 이미 증명했는데도 말입니다. 기록 갱신을 위한 탐색도 계속되고 있습니다. GIMPS 프로젝트의 참가자들은 2^p − 1 형태의 메르센 수를 나누어 조사하고 있으며, 현재 알려진 가장 큰 소수는 2024년에 발견된 2¹³⁶²⁷⁹⁸⁴¹ − 1로 41,024,320자리에 이릅니다.

모든 여담 보기

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	101	103	107	109	113	127	131	137	139	149	151
157	163	167	173	179	181	191	193	197	199	211	223
227	229	233	239	241	251	257	263	269	271	277	281
283	293	307	311	313	317	331	337	347	349	353	359
367	373	379	383	389	397	401	409	419	421	431	433
439	443	449	457	461	463	467	479	487	491	499	503
509	521	523	541	547	557	563	569	571	577	587	593
599	601	607	613	617	619	631	641	643	647	653	659
661	673	677	683	691	701	709	719	727	733	739	743
751	757	761	769	773	787	797	809	811	821	823	827
829	839	853	857	859	863	877	881	883	887	907	911
919	929	937	941	947	953	967	971	977	983	991	997

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	101	103	107	109	113	127	131	137	139	149	151
157	163	167	173	179	181	191	193	197	199	211	223
227	229	233	239	241	251	257	263	269	271	277	281
283	293	307	311	313	317	331	337	347	349	353	359
367	373	379	383	389	397	401	409	419	421	431	433
439	443	449	457	461	463	467	479	487	491	499	503
509	521	523	541	547	557	563	569	571	577	587	593
599	601	607	613	617	619	631	641	643	647	653	659
661	673	677	683	691	701	709	719	727	733	739	743
751	757	761	769	773	787	797	809	811	821	823	827
829	839	853	857	859	863	877	881	883	887	907	911
919	929	937	941	947	953	967	971	977	983	991	997