Problem 7 - 10,001st Prime

Landscape aerial view overlooking Lion Rock & surroundings from above Pidurangala
Sigiriya, Sri Lanka - May 2nd, 2025

By listing the first six prime numbers: \(2, 3, 5, 7, 11, 13\), we can see that the 6th prime is \(13\).
What is the \(10,001\)st prime number?

https://projecteuler.net/problem=7

Development

The Sieve of Eratosthenes is important here. Resource:

• https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html

It is said that \(n * ln(n)\) is a good estimate of the \(n\)^th prime.

Thus, we implement the logic below as a crude implementation of the sieve where we pre-generate a sequence of values: setting our lower bound to 2, and our upper bound to \(2 * n * ln(n)\) where \(n\) is the \(n\)^th prime.

In the sieve, we eliminate values incremntally from the pre-generated set by conducting remainder division to reach the next prime until we reach the \(n\)^th prime. This pattern allows us to conduct divisibility by the lowest prime of 2, then 3, 5, 7, etc., & we do not even need to check for primeness.

The sieve is pretty neat!

R

Answer 1

n <- 10001

sieve <- function(n) {
  n1 <- 2
  n2 <- 2*ceiling(n*log(n))
  p <- n1:n2
  for(i in 2:n) {
    # incremental elimination
    p <- p[p %% p[1] != 0]
  }
  return(c(p[1], max=n2))
}

tic()
sieve(n)
toc()

          max 
104743 184228 
0.839 sec elapsed

Answer 2

tic()
primes::nth_prime(10001)
toc()

[1] 104743
0.036 sec elapsed

Python

Answer 1

import time
from math import ceil, log

def sieve(n: int) -> int:
  n1 = 2
  n2 = 2*ceil(n*log(n))
  p = list(range(2, n2+1))
  for i in range(2, n+1):
    p = [j for j in p if j % p[0] != 0]
  return(p[0])

n = 10001
t0 = time.perf_counter()
print(sieve(n))
t1 = time.perf_counter()
t = t1 - t0
print(f'{t:.3f} sec elapsed')

104743
3.841 sec elapsed

Answer 2

import sympy

t0 = time.perf_counter()
print(sympy.prime(10001))
t1 = time.perf_counter()
t = t1 - t0
print(f'{t:.3f} sec elapsed')

104743
0.007 sec elapsed