에라토스테네스의 체 계산기
N 이하의 소수를 배수를 지워나가는 고전 알고리즘으로 걸러냅니다. 소수 목록과 쌍둥이 소수도 함께 보여줍니다.
최대 1,000,000까지
소수 개수25개
쌍둥이 소수 쌍8쌍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
소수 목록
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몇까지의 소수를 구할지 입력합니다.
- 2소수 개수·목록·쌍둥이 소수를 확인합니다.
자주 묻는 질문
2부터 시작해 그 배수(4, 6, 8, …)를 전부 지우고, 다음으로 지워지지 않은 수(3)의 배수를 지우는 식으로 반복합니다. 끝까지 지워지지 않고 남는 수가 소수입니다. 기원전 3세기 그리스 수학자 에라토스테네스의 이름을 땄습니다.
i의 배수 중 i²보다 작은 것들(2i, 3i, …)은 이미 더 작은 소인수를 지울 때 먼저 지워졌기 때문입니다. 예를 들어 7의 배수 중 14(2×7), 21(3×7), 28(4×7), 35(5×7), 42(6×7)는 2, 3, 5의 배수를 지우는 단계에서 이미 지워졌으므로, 7의 배수는 49(7×7)부터 지우면 충분합니다.
차이가 2인 소수 쌍입니다(예: 3과 5, 11과 13, 17과 19). 소수가 커질수록 점점 드물어지지만 이런 쌍이 무한히 있는지는 아직 증명되지 않은 유명한 미해결 문제(쌍둥이 소수 추측)입니다.
각 소수 p마다 n/p번 지우는 연산을 하는데, 소수의 역수를 모두 더한 값(1/2+1/3+1/5+1/7+…)이 발산하긴 하지만 log log n 만큼만 아주 느리게 커지기 때문입니다(메르텐스 제2정리). 그래서 전체 지우는 횟수가 n log log n에 비례합니다.
알아두면 좋은 점
- 최대 1,000,000까지 계산합니다. 그보다 크면 브라우저 메모리·속도에 부담이 됩니다.
- 격자는 400 이하일 때만 시각적으로 그립니다. 그보다 크면 목록으로만 보여줍니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.