Project Euler 7: 10001번째 소수를 크기를 두 배씩 늘리는 에라토스테네스의 체로 구하기
n번째 소수를 구할 때 체의 크기를 미리 알 수 없다는 문제를, 체를 두 배씩 키우는 방법으로 풉니다. 시행 나눗셈에서 출발해 에라토스테네스의 체를 유도하고, 두 배로 키워도 일이 두 배 남짓에 그치는 이유와 C++17·Python 3 구현까지 다룹니다.
스포일러 주의 · 이 글에는 풀이 과정과 정답이 그대로 나옵니다. 직접 먼저 풀어 보고 싶다면 Project Euler 7번 문제부터 보세요.
Project Euler 시리즈의 일곱 번째 문제입니다. 소수를 차례로 세는 문제라 3번 문제의 시행 나눗셈을 그대로 써도 답은 나옵니다. 이 글은 한 걸음 더 나아가 에라토스테네스의 체를 끌어내고, 체를 쓸 때 늘 부딪히는 질문인 “어디까지 체를 쳐야 하나?“에 근거 없는 상수 대신 체를 두 배씩 키우는 방법으로 답합니다. 체는 10번 문제 같은 뒤의 문제에서도 다시 쓰는 도구입니다.
스포일러 주의: 이 글에는 풀이 전체와 정답이 들어 있습니다. 직접 먼저 풀어 보고 싶다면 원래 문제부터 보세요. 이 시리즈의 글에는 광고를 싣지 않습니다. 문제 본문의 라이선스(CC BY-NC-SA 4.0)가 비영리 조건을 두기 때문입니다.
문제
소수를 작은 것부터 늘어놓으면 처음 여섯 개는 2, 3, 5, 7, 11, 13이고, 여섯 번째 소수는 13입니다. 같은 방식으로 셌을 때 10001번째 소수를 구하는 것이 문제입니다.
따로 받는 입력은 없고 n은 10001로 정해져 있습니다. 구할 것은 정수 하나입니다. 이 글에서는 n번째 소수를 pₙ으로 씁니다(p₁ = 2, p₆ = 13).
필요한 배경 지식
소수와 합성수. 1보다 큰 정수 중 약수가 1과 자기 자신뿐인 수가 소수, 그 밖의 1보다 큰 정수가 합성수입니다. 1은 어느 쪽도 아닙니다. 그래서 순서를 세는 시작은 p₁ = 2입니다.
√m까지만 나눠 보면 되는 이유. 합성수 m = a × b(1 < a ≤ b)라면 a × a ≤ a × b = m이므로 a ≤ √m입니다. 즉 합성수에는 반드시 √m 이하의 약수가 있습니다. 거꾸로, 2부터 √m까지 어떤 수로도 나누어떨어지지 않는 m ≥ 2는 소수입니다. 코드에서는 d × d ≤ m 대신 같은 뜻인 d ≤ m / d(정수 나눗셈)를 써서 곱셈이 넘칠 걱정을 없앱니다. 양의 정수에서 d ≤ ⌊m / d⌋와 d × d ≤ m은 정확히 같은 조건입니다.
가장 작은 약수는 소수입니다. m ≥ 2의 1보다 큰 약수 중 가장 작은 것을 q라 하면 q는 소수입니다. q가 합성수라면 q보다 작은 약수가 있고, 그것은 m의 약수이기도 해서 q가 가장 작다는 데 모순입니다. 아래 두 증명에서 씁니다.
소수는 끝이 없습니다(유클리드). 소수가 p₁, …, pₖ뿐이라고 해 봅시다. N = p₁ × … × pₖ + 1의 가장 작은 약수는 소수인데, N을 어느 pᵢ로 나눠도 나머지가 1이므로 그 소수는 목록에 없습니다. 모순이므로 소수는 무한히 많습니다. 이 사실이 “체를 계속 키우면 언젠가 n개를 모은다”는 것, 즉 아래 알고리즘이 끝난다는 근거입니다.
에라토스테네스의 체. 0부터 L까지의 수를 늘어놓고, 2부터 차례로 “아직 지워지지 않은 수”를 소수로 확정한 뒤 그 수의 배수를 지워 나가는 방법입니다. 끝나면 지워지지 않은 2 이상의 수가 정확히 L 이하의 소수입니다. “풀이 유도”에서 단계별로 만들어 봅니다.
가장 단순한 방법
2부터 수를 하나씩 올리며 시행 나눗셈으로 소수인지 확인하고, n번째 소수가 나오면 멈춥니다.
def is_prime(m):
if m < 2:
return False
d = 2
while d <= m // d:
if m % d == 0:
return False
d += 1
return True
count = 0
m = 1
while count < 10001:
m += 1
if is_prime(m):
count += 1
# 이제 m이 10001번째 소수이 방법은 맞고, 미리 상한을 알 필요도 없습니다. 비용은 수 m 하나에 나눗셈이 많아야 √m번이므로, pₙ까지 모든 수를 검사하면 전체가 많아야 pₙ × √pₙ 정도, 즉 O(pₙ√pₙ) 입니다. 합성수는 작은 약수에서 일찍 멈추지만, 소수 n개는 매번 √m까지 다 나눠 봐야 하므로 비용의 대부분을 차지합니다. n = 10001에서는 이것도 충분히 빠르지만, n이 커지면 √pₙ배가 빠르게 커집니다. 수 하나하나에 “소수냐”고 묻는 대신, 소수에서 출발해 배수를 한꺼번에 지우면 이 √pₙ배를 거의 없앨 수 있습니다. 그것이 체입니다.
풀이 유도
1단계: 문제의 예를 손으로 확인합니다. 2부터 시작해 소수를 세면 2(1번째), 3(2번째), 5(3번째), 7(4번째), 11(5번째), 13(6번째)입니다. 그 사이의 4, 6, 8, 9, 10, 12는 각각 2나 3으로 나누어떨어집니다. p₆ = 13이 문제의 예와 같습니다.
2단계: 묻는 대신 지웁니다. 시행 나눗셈은 m마다 “어떤 작은 수가 m을 나누나?“를 묻습니다. 반대로 소수 p를 하나 찾을 때마다 p의 배수를 모두 “합성수”로 표시하면, 어떤 수에 다다랐을 때 표시가 없다는 것만으로 소수임을 알 수 있습니다. L = 16에서 해 보면 다음과 같습니다.
i = 2: 표시 없음 → 소수. 4, 6, 8, 10, 12, 14, 16을 지움
i = 3: 표시 없음 → 소수. 9, 12, 15를 지움 (6은 이미 지워짐)
i = 4: 지워져 있음 → 건너뜀
i = 5: 표시 없음 → 소수. 5 × 5 = 25 > 16이라 지울 것 없음
i = 6 … 16: 7, 11, 13만 표시 없음 → 소수
결과: 2, 3, 5, 7, 11, 13여섯 개가 나오고 여섯 번째가 13입니다. 1단계와 같습니다.
3단계: 지우기는 i × i부터, i × i > L이면 생략합니다. 소수 i의 배수 k × i 중 k < i인 것은 k의 소인수(i보다 작은 소수)의 배수이므로 그 소수를 처리할 때 이미 지워졌습니다. 그래서 i × i부터 지워도 빠지는 수가 없습니다. 위의 i = 3에서 6을 다시 지우지 않은 것이 그 예입니다. 같은 이유로 i × i > L이면 지울 것이 없고, 그런 i는 표시만 확인해 소수 목록에 넣습니다.
4단계: 체에는 상한이 필요한데, 우리는 pₙ의 크기를 모릅니다. 체는 “L 이하의 소수 전부”를 주는 도구이고, 문제는 “n번째 소수”를 묻습니다. 흔한 방법은 적당히 큰 L을 정해 두는 것이지만, 그 L이 충분하다는 근거가 없으면 맞는 답이라는 보장도 없습니다. 이 글은 L을 미리 정하지 않습니다.
- L = 16에서 체를 칩니다.
- 얻은 소수가 n개 이상이면 그중 n번째를 돌려줍니다.
- 모자라면 L을 두 배로 늘려 처음부터 다시 칩니다.
왜 n개 이상이면 그 n번째가 답인가. 체는 L 이하의 소수를 빠짐없이, 작은 것부터 줍니다. 그러니 목록의 n번째는 “n번째로 작은 소수”, 곧 pₙ입니다. 목록이 L 이하만 담는다는 것은 상관없습니다. pₙ보다 작은 소수는 모두 pₙ ≤ L보다도 작으니 목록에 다 들어 있습니다.
왜 끝나는가. 소수는 무한히 많으므로 L을 계속 두 배로 늘리면 언젠가 L ≥ pₙ이 되고, 그때 목록에는 n개 이상이 들어 있습니다.
작은 예로 따라가 봅니다. n = 6이면 L = 16의 첫 체에서 여섯 개를 모으므로 바로 13을 돌려줍니다. n = 7이면 L = 16에서는 여섯 개뿐이라 모자라고, L = 32로 다시 치면 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31의 열한 개가 나와 일곱 번째인 17을 돌려줍니다.
5단계: 두 배로 키워도 낭비는 크지 않습니다. 첫 L = 16에서 끝나지 않았다고 해 봅시다. 마지막 체의 크기가 L이면 직전 체 L / 2에서는 소수가 n개 미만이었으므로 pₙ > L / 2이고, 마지막 체에서 끝났으므로 pₙ ≤ L입니다.
L / 2 < pₙ ≤ L, 즉 L < 2pₙ마지막 체는 필요한 크기의 두 배를 넘지 않습니다. 앞선 체들까지 모두 더해도 16 + 32 + … + L < 2L < 4pₙ이라, 처음부터 정확한 상한을 알고 한 번만 친 경우에 비해 상수 배만 더 듭니다. 이것이 미리 증명된 상한 없이도 쓸 수 있는 이유입니다.
최종 알고리즘
primes_up_to(L): 크기 L + 1의 표시 배열을 만들고, i = 2부터 L까지 표시가 없으면 소수 목록에 넣고, i ≤ L / i이면 i × i, i × i + i, …를 지웁니다.nth_prime(n): L = 16에서 시작해 목록에 n개 이상이 될 때까지 L을 두 배로 늘리며 1을 반복하고, 목록의 n번째(0부터 세면 n − 1번 칸)를 돌려줍니다.- 정답을 출력하기 전에 확인합니다. p₁ = 2, p₆ = 13이어야 하고, 시행 나눗셈으로 찾은 처음 100개의 소수와
nth_prime(1)부터nth_prime(100)까지가 모두 같아야 합니다. 하나라도 다르면 0이 아닌 종료 코드로 끝냅니다.
정확성 증명
- 소수는 지워지지 않습니다. 지워지는 수는 i × i + k × i = i × (i + k)(i ≥ 2, k ≥ 0) 꼴이라 1보다 큰 두 수의 곱, 곧 합성수입니다.
- L 이하의 합성수는 모두 지워집니다. 합성수 m ≤ L의 가장 작은 약수 q는 소수이고, 배경 지식대로 q ≤ √m ≤ √L입니다. 차례가 i = q일 때 q는 지워져 있지 않고(소수이므로), q ≤ L / q이므로 지우기를 합니다. m = q × (m / q)이고 m / q ≥ q이므로 m은 q × q부터 시작하는 지우기 범위 안에 있습니다. 그리고 q < m이라 m에 다다르기 전에 이 일이 끝납니다.
- 따라서 i에 다다랐을 때 표시가 없다는 것은 i가 소수라는 것과 같고, i를 2부터 L까지 차례로 보므로 목록은 L 이하의 소수 전부를 작은 순서대로 담습니다.
- 4단계에서 보인 대로 목록이 n개 이상이면 n번째는 pₙ이고, 소수가 무한하므로 반복은 끝납니다.
복잡도
크기 L의 체 한 번에 드는 일을 셋으로 나눠 봅니다.
- 체 만들기(지우기). 소수 p ≤ √L마다 많아야 L / p개를 지웁니다. 모든 i ≤ √L에 대해 L / i를 더해도 L × (1 + 1/2 + … ) = O(L log L)이므로 이것이 손쉬운 상한입니다. 소수의 역수 합이 log log 정도로만 자란다는 알려진 결과(메르텐스의 정리)를 쓰면 더 정확히 O(L log log L) 입니다.
- 훑기(목록 만들기). 바깥 반복은 i = 2부터 L까지 한 번씩 표시를 확인하므로 O(L)입니다.
- 고르기. 목록의 n − 1번 칸을 읽는 것은 O(1)입니다.
두 배로 키우는 반복 전체로는, 5단계대로 체 크기의 합이 2L 미만이고 L < 2pₙ(첫 체에서 끝나면 L = 16)이므로 전체 시간은 O(pₙ log log pₙ), 공간은 표시 배열 L + 1칸과 소수 목록을 합쳐 O(pₙ) 입니다. 소수 정리에 따르면 pₙ은 대략 n ln n이므로 n에 대해 쓰면 O(n log n)보다 조금 큰 정도입니다. 가장 단순한 방법의 O(pₙ√pₙ)과 비교하면 √pₙ배가 log log pₙ배로 줄었습니다.
이 글은 소수 정리나 pₙ의 명시적 상한을 알고리즘의 근거로 쓰지 않습니다. 위의 대략적인 크기는 비용을 가늠하려는 것뿐이고, 정확성은 두 배로 키우기만으로 보장됩니다.
정수와 인덱스 범위.
- 저장되는 값은 모두 마지막 L 이하입니다. 표시 배열의 인덱스는 0부터 L까지이고, 목록에 담기는 소수도 모두 L 이하입니다. L을 넘을 수 있는 것은 잠깐 쓰이는 루프 값뿐입니다. 마지막 j += i 뒤의 j는 j + i < 2L까지 가고, 배열에 넘기는 크기 L + 1도 L보다 1 큽니다. 두 배로 키우는
limit *= 2는 체가 모자랄 때만 실행되므로, 그 결과 중 가장 큰 값은 마지막 L 자체입니다. n = 10001에서 마지막 L은 131072이므로(“정답과 검증” 참고), 잠깐 쓰이는 값까지 포함해 모든 값이 2 × 131072 = 262144 미만이고 부호 없는 32비트 범위에 넉넉히 들어갑니다. 일반적인 조건은 세 번째 항목에 있습니다. - C++에서는 값과 인덱스를 모두
std::size_t로 둡니다. 표시 배열이 실제로 L + 1칸을 차지하므로, 그 배열을 만들 수 있는 환경이라면 L은std::size_t로 표현됩니다. - 곱셈 i × i는 i ≤ L / i를 확인한 뒤에만 계산하므로 i × i ≤ L이라 넘치지 않습니다. 지우기의 j += i는 j ≤ L, i ≤ L에서 출발하므로 많아야 2L이고, L × 2(다음 체 크기)와 함께 L이
std::size_t최댓값의 절반 이하인 한 넘치지 않습니다. 그 크기의 배열은 메모리가 먼저 모자라므로 현실적인 제약은 메모리입니다. nth_prime은 n ≥ 1을 전제합니다. n − 1번 칸을 읽기 때문입니다(아래 “경계 사례”).std::vector<bool>은 표준이 공간 절약형 특수화로 정해 두었고, 흔한 구현은 한 칸을 1비트로 저장합니다. Python의bytearray는 한 칸에 1바이트를 씁니다. Python의int는 정밀도에 제한이 없어 넘칠 일이 없습니다.
C++17 구현
#include <cstddef>
#include <iostream>
#include <vector>
// Sieve of Eratosthenes over 0..limit. Returns every prime <= limit in increasing order.
std::vector<std::size_t> primes_up_to(std::size_t limit) {
std::vector<bool> composite(limit + 1, false);
std::vector<std::size_t> primes;
for (std::size_t i = 2; i <= limit; ++i) {
if (composite[i]) {
continue;
}
primes.push_back(i);
// i <= limit / i is i * i <= limit without computing i * i.
if (i <= limit / i) {
for (std::size_t j = i * i; j <= limit; j += i) {
composite[j] = true;
}
}
}
return primes;
}
// The n-th prime, for n >= 1. Doubles the sieve limit until the sieve holds at
// least n primes, so no bound on the n-th prime has to be known in advance.
std::size_t nth_prime(std::size_t n) {
std::size_t limit = 16;
while (true) {
const std::vector<std::size_t> primes = primes_up_to(limit);
if (primes.size() >= n) {
return primes[n - 1];
}
limit *= 2;
}
}
// Trial division. Used only to cross-check the sieve.
bool is_prime_by_trial(std::size_t m) {
if (m < 2) {
return false;
}
for (std::size_t d = 2; d <= m / d; ++d) {
if (m % d == 0) {
return false;
}
}
return true;
}
int main() {
if (nth_prime(1) != 2 || nth_prime(6) != 13) {
return 1;
}
std::size_t count = 0;
for (std::size_t m = 2; count < 100; ++m) {
if (is_prime_by_trial(m)) {
++count;
if (nth_prime(count) != m) {
return 1;
}
}
}
std::cout << nth_prime(10001) << '\n';
return 0;
}is_prime_by_trial은 가장 단순한 방법의 시행 나눗셈을 그대로 옮긴 함수이고, 처음 100개의 소수에서 체와 같은 답을 내는지 대조하는 데만 씁니다. 체의 지우기 범위나 두 배로 키우는 반복에 실수가 있다면 이 대조에서 걸립니다. 작은 예의 확인은 assert가 아니라 if로 했습니다. assert는 NDEBUG가 정의된 빌드에서 아무 일도 하지 않지만, if의 비교와 return 1은 프로그램의 관찰 가능한 동작이라 -O2 최적화로도 없어지지 않습니다.
Python 3 구현
def primes_up_to(limit: int) -> list[int]:
"""Sieve of Eratosthenes over 0..limit. Returns every prime <= limit in increasing order."""
composite = bytearray(limit + 1)
primes = []
for i in range(2, limit + 1):
if composite[i]:
continue
primes.append(i)
# The range is empty when i * i > limit.
for j in range(i * i, limit + 1, i):
composite[j] = 1
return primes
def nth_prime(n: int) -> int:
"""The n-th prime, for n >= 1.
Doubles the sieve limit until the sieve holds at least n primes, so no bound
on the n-th prime has to be known in advance.
"""
limit = 16
while True:
primes = primes_up_to(limit)
if len(primes) >= n:
return primes[n - 1]
limit *= 2
def is_prime_by_trial(m: int) -> bool:
"""Trial division. Used only to cross-check the sieve."""
if m < 2:
return False
d = 2
while d <= m // d:
if m % d == 0:
return False
d += 1
return True
def main() -> None:
if nth_prime(1) != 2 or nth_prime(6) != 13:
raise SystemExit(1)
count = 0
m = 2
while count < 100:
if is_prime_by_trial(m):
count += 1
if nth_prime(count) != m:
raise SystemExit(1)
m += 1
print(nth_prime(10001))
if __name__ == "__main__":
main()C++와 같은 알고리즘, 같은 확인입니다. C++의 if (i <= limit / i)에 해당하는 조건은 따로 쓰지 않았습니다. i × i > L이면 range(i * i, limit + 1, i)가 비어 있어 같은 일을 하기 때문입니다. bytearray(limit + 1)은 모든 칸이 0(표시 없음)으로 시작합니다. 작은 예가 틀리면 raise SystemExit(1)로 종료 코드 1을 냅니다. assert는 python -O로 실행하면 제거되므로 쓰지 않았습니다.
정답과 검증
10001번째 소수는 104743입니다.
손으로 따라갈 수 있는 부분은 다음과 같습니다.
- 체의 크기. 체는 16, 32, 64, …로 커지며, 2¹⁶ = 65536 < p₁₀₀₀₁ ≤ 2¹⁷ = 131072이므로 L = 65536까지는 소수가 모자라고 L = 131072에서 멈춥니다. 5단계의 L / 2 < pₙ ≤ L과 맞습니다.
- 소수인지. 위 값은 홀수이고, 각 자리 숫자의 합이 19라 3의 배수가 아니며, 끝자리가 0이나 5가 아니라 5의 배수도 아닙니다. 소수라는 완전한 확인은 제곱근 이하(323 이하)의 모든 수로 나눠 보는 시행 나눗셈이 필요하고, 그 일은 손 대신 프로그램이 합니다.
검증은 세 겹입니다.
- 작은 예와 처음 100개 대조. 두 프로그램 모두 답을 출력하기 전에 p₁ = 2, p₆ = 13을 확인하고, 시행 나눗셈으로 찾은 처음 100개의 소수와 체가 낸 1번째부터 100번째까지가 모두 같은지 확인합니다. 하나라도 다르면 0이 아닌 종료 코드로 끝납니다. p₆ = 13과 p₇ = 17은 “풀이 유도”에서 손으로도 따라가 보았습니다.
- 두 구현의 일치. 이 시리즈의 저장소에서는 검사 스크립트가 C++ 코드를
g++ -std=c++17 -O2 -Wall -Wextra -Werror로 컴파일해 실행하고(경고도 실패로 처리), Python 코드를python3 -I -B로 실행합니다. 두 출력이 저장해 둔answer.txt와 바이트 단위로 같아야 하고, 0이 아닌 종료 코드나 시간 초과(C++ 1초, Python 10초)는 실패입니다. 시리즈 규칙상 이 검사를 통과한 코드만 글에 싣습니다. - 증명. 체가 L 이하의 소수를 정확히 내는 것과, 두 배로 키우는 반복이 pₙ을 돌려주고 끝난다는 것은 “풀이 유도”와 “정확성 증명”에서 보였습니다.
경계 사례
- n = 1: 첫 체(L = 16)의 첫 원소 2를 돌려줍니다. 1은 소수가 아니라서 목록에 들어가지 않습니다(바깥 반복이 i = 2부터 시작). 작은 예에 p₁ = 2가 들어 있습니다.
- n = 6: 첫 체에 정확히 여섯 개가 있어 두 배로 키우지 않고 끝납니다. 크기 비교가
>=인 덕분이고,>로 잘못 쓰면 쓸데없이 한 번 더 체를 칩니다(답은 같지만). - n = 7: 처음으로 체를 키워야 하는 경우이고, L = 32에서 17을 돌려줍니다.
- n = 0: 0번째 소수라는 것은 없고 함수는 n ≥ 1을 전제합니다. 이 경우 C++에서는 n − 1이 부호 없는 정수에서 최댓값으로 돌아가 범위를 벗어난 접근이 되고, Python에서는
primes[-1]이 마지막 원소를 조용히 돌려줍니다. 이 프로그램은 n ≥ 1로만 부르지만, 다른 곳에 재사용한다면 입력을 먼저 확인해야 합니다. - 시작 크기: 16은 문제의 예가 첫 체에 들어가도록 고른 값일 뿐이고, 1 이상이면 어떤 값이든 맞습니다. 0에서 시작하면 두 배를 해도 0이라 끝나지 않습니다.
- i × i의 지우기 시작: 2 × i부터 지워도 답은 같지만 이미 지운 수를 다시 지우는 일이 늘어납니다. 반대로 i × i 대신 그보다 큰 수에서 시작하면 합성수가 남아 틀린 답이 나옵니다.
더 생각해 볼 것
- 한 번만 치기. pₙ의 증명된 명시적 상한을 알면 체를 한 번만 칠 수 있습니다. 그 경우 상한이 정말 성립하는 n의 범위를 함께 확인해야 합니다. 두 배로 키우기는 그런 확인 없이 많아야 상수 배의 일을 더 하는 대신 안전하게 끝납니다.
- 홀수만 체로 치기. 2를 따로 처리하고 홀수만 배열에 담으면 메모리와 일이 대략 절반으로 줄어듭니다. 인덱스와 수의 대응(칸 k가 수 2k + 1)을 직접 맞춰 보세요.
- 다시 치지 않기. 지금은 L을 두 배로 늘릴 때마다 처음부터 다시 칩니다. 앞서 찾은 소수로 새로 늘어난 구간 (L, 2L]만 치도록 바꿀 수 있을까요? 구간마다 지우기를 어디서 시작해야 하는지가 핵심입니다(구간 체, segmented sieve).
- 관련 문제. 이 시리즈 3번 문제는 시행 나눗셈으로 소인수를 찾았습니다. 10번 문제는 정해진 상한 아래의 소수를 모두 다루므로, 상한을 아는 경우의 체를 그대로 쓸 수 있습니다.
출처와 라이선스
- Project Euler, Problem 7 — 원래 문제. 이 글의 “문제” 절은 그 내용을 직접 요약한 것이고, 원문과 같은 CC BY-NC-SA 4.0으로 공유합니다. 문제의 저작자 표시는 Project Euler입니다.
- Project Euler, Copyright — 문제 본문의 라이선스와 링크 방식. 비영리 조건에 따라 이 글에는 광고를 싣지 않습니다(
ads: false). std::vector<bool>은 C++ 표준 작업 초안 [vector.bool],assert와NDEBUG는 [assertions.assert]를 따랐습니다. Python의assert와-O는 The assert statement,bytearray는 Bytearray Objects를 따랐습니다.- 메르텐스의 정리와 소수 정리는 복잡도의 크기를 가늠하는 데만 인용한 잘 알려진 정수론의 결과이고, 이 글에서 증명하지 않았습니다. 알고리즘의 정확성은 이 두 결과에 기대지 않습니다.
- 풀이, 증명, 코드는 직접 쓴 것입니다. Project Euler의 해설(overview), 포럼, 회원 전용 자료나 다른 풀이 사이트는 참고하지 않았습니다. Motitory는 Project Euler와 제휴나 후원 관계가 없고, Project Euler가 이 글을 검토하지도 않았습니다.