소수 생성기

소수, 즉 1보다 크고 약수가 1과 자기 자신뿐인 자연수를 나열합니다. 1부터 100까지나 1조 미만의 마지막 100만 개의 수 같은 범위의 모든 소수, 또는 처음 N개의 소수를 요청할 수 있습니다. 개수, 찾은 가장 작은 소수와 가장 큰 소수, 그 합, 쉼표로 구분된 복사용 목록을 알려 줍니다.

사용 방법

1. 범위 또는 '처음 N개의 소수'를 고릅니다.
2. 범위라면 시작과 끝을 입력합니다. 양 끝 모두 포함됩니다.
3. 처음 N개의 소수라면 N을 입력합니다.
4. 결과 상자에서 목록을 복사하거나, 표에서 10개씩 나뉜 행으로 확인합니다.

계산식

Sieve of Eratosthenes: for each prime p ≤ √(end), cross out p², p² + p, p² + 2p, … — every number left is prime.

모든 합성수 n은 √n 이하의 약수를 가지므로 끝의 제곱근까지의 소수만 있으면 됩니다. 시작이 큰 범위에서는 구간 체를 사용합니다. 요청한 수에 대해서만, 그 작은 소수들로 체를 돌리므로 큰 시작점 아래의 모든 정수를 할당하지 않아도 됩니다. 기초 소수를 준비하는 작업은 여전히 필요합니다. 처음 N개의 소수는 N(ln N + ln ln N)까지 체를 돌리며, 이 값은 N ≥ 6에서 N번째 소수보다 크다고 증명되어 있습니다.

예시

1부터 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. 가장 작은 소수는 2, 가장 큰 소수는 97이며, 모두 더하면 1,060입니다.