수학

소수 판별기 (1~1,000만까지)

정수 N(최대 1,000만)이 소수인지 즉시 판별합니다. 시험 나눗셈 단계, 이전·다음 소수, 소인수분해를 표시합니다.

처음 100개의 소수 목록

#1–10	#2–11	#3–12	#4–13	#5–14	#6–15	#7–16	#8–17	#9–18	#10–19
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

소수란 1보다 큰 정수 중에서 1과 자기 자신 이외에 약수가 없는 수입니다. 2, 3, 5, 7, 11, 13, … 순서로 이어집니다.
가장 기본적인 소수 판별법은 시험 나눗셈법입니다. 2부터 √N까지의 정수로 차례로 나누어 보고, 어느 것으로도 나누어지지 않으면 소수로 판별합니다.
1은 소수가 아닙니다. 소수의 정의는 "1보다 큰"을 요구합니다. 또한 2는 유일한 짝수 소수입니다.
소수는 무한히 존재합니다(기원전 300년경 유클리드가 증명). 그러나 수가 커질수록 소수의 출현 빈도는 낮아집니다(소수 정리: n 근방에서 소수의 밀도 ≈ 1/ln(n)).

2는 1과 자기 자신 이외에 약수가 없으므로 소수입니다. 유일한 짝수 소수이기도 합니다. 다른 모든 짝수는 2의 배수이므로 소수가 될 수 없습니다.

소수의 정의가 "1보다 큰 정수로서 1과 자기 자신 이외에 약수가 없는 것"이기 때문에 1은 제외됩니다. 산술의 기본정리(소인수분해의 유일성)를 성립시키기 위해서도 1을 소수에서 제외하는 것이 수학적으로 편리합니다.

N에 대해 O(√N)의 계산량이 필요합니다. 이 도구는 N ≤ 10,000,000에 대응하며, √10,000,000 ≈ 3162이므로 최대 3162번의 나눗셈으로 판별할 수 있습니다.

소수는 "수의 원자"라 불립니다. 모든 정수는 소수의 곱으로 유일하게 나타낼 수 있다는 산술의 기본정리(소인수분해의 유일성)가 그 근거입니다.

현대의 RSA 암호는 두 개의 큰 소수의 곱(예: 2048비트)을 만드는 것은 쉽지만, 그 곱을 소인수분해하는 것은 현대 컴퓨터로도 사실상 불가능하다는 비대칭성을 이용합니다. 인터넷의 HTTPS 통신과 전자서명의 보안을 소수가 지탱하고 있습니다.

#1–10	#2–11	#3–12	#4–13	#5–14	#6–15	#7–16	#8–17	#9–18	#10–19
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

#1–10	#2–11	#3–12	#4–13	#5–14	#6–15	#7–16	#8–17	#9–18	#10–19
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

#1–10	#2–11	#3–12	#4–13	#5–14	#6–15	#7–16	#8–17	#9–18	#10–19
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