이 계산기가 하는 일
하나의 도구에 소수 관련 기능 세 가지를 담았습니다. 이 계산기는 (1) n번째 소수를 찾아 주고(\(\text{Prime}[n] = p_n\)), (2) 입력한 정수가 소수인지 판별하면서 소수 수열에서 몇 번째인지 알려 주며, (3) 원하는 만큼 처음 N개의 소수를 나열해 줍니다. 가장 작은 소수부터 나열하면 2, 3, 5, 7, 11, 13, 17, … 순입니다. 소수란 1보다 큰 정수 중에서 양의 약수가 1과 자기 자신뿐인 수를 말합니다.
사용 방법
먼저 모드를 고르세요. n번째 소수 모드에서는 1부터 세는 순서 n(예: 100)을 입력하면 \(\text{Prime}[100] = 541\)을 돌려줍니다. 소수 판별 모드에서는 아무 정수(예: 97)나 입력하면 그 수가 소수인지, 소수라면 소수 수열에서 몇 번째 n인지 알려 줍니다. 처음 N개 소수 나열 모드에서는 원하는 개수를 입력하면 쉼표로 구분된 전체 목록과 함께 가장 큰 소수 \(\text{Prime}[N]\)을 보여 줍니다.
공식 설명
소수 판별은 시험 나눗셈(trial division) 방식으로 이루어집니다. 어떤 수 \(p\)는 2부터 \(\sqrt{p}\) 사이에 약수가 하나도 없을 때 소수입니다.
$$p \text{ prime} \iff p \ge 2 \;\wedge\; \nexists\, d \in [2,\sqrt{p}\,]: d \mid p$$
2를 먼저 처리한 뒤에는 홀수 약수 \(d\)만 \(d\times d \le p\)인 동안 확인하면 되므로, 빠르면서도 부동소수점 오차를 피할 수 있습니다. n번째 소수는 후보 2, 3, 4, …를 차례로 훑으며 소수를 하나씩 세어 개수가 n에 도달할 때 찾아냅니다. 소수 \(m\)의 순서(소수 인덱스)는 \(\pi(m)\), 즉 \(m\) 이하의 소수 개수와 같습니다.
풀이 예시
97을 판별해 봅시다. 97은 홀수이므로 \(d = 3, 5, 7, 9\)를 차례로 시험합니다(\(9^2 = 81 \le 97\)이지만 \(11^2 = 121 > 97\)이기 때문입니다). 어느 것으로도 97이 나누어떨어지지 않으므로 97은 소수입니다. 97까지의 소수를 세어 보면 2, 3, 5, …, 97로 모두 25개이므로, 97은 25번째 소수입니다(\(\text{primeIndex} = 25\)).
자주 묻는 질문
1은 소수인가요? 아닙니다. 정의상 소수는 1보다 커야 하므로, 1은 소수도 합성수도 아닙니다.
유일한 짝수 소수는 무엇인가요? 2가 유일한 짝수 소수입니다. 그 외의 모든 짝수는 2로 나누어떨어지기 때문입니다.
100번째 소수는 무엇인가요? \(\text{Prime}[100] = 541\)입니다. 참고 지점 몇 가지를 더 들면 \(\text{Prime}[10] = 29\), \(\text{Prime}[25] = 97\), \(\text{Prime}[50] = 229\), \(\text{Prime}[223] = 1409\)입니다.
