Problem: What is the 10,001st prime number?
Q. How do we find the nth prime number?
A. Build a Sieve of Eratosthenes large enough to contain the nth prime number.
Q. What size must a sieve be to contain the nth prime number?
A. There is no known formula which would tell us the exact position of the nth prime number. However, there are numerous ways to estimate the number of primes below a given number (see Prime-counting function), with varying degrees of accuracy. For our purposes, we can use a simplified formula by assuming that at least 1% of numbers are prime, and therefore the nth prime number will occur by 100 x n (e.g. the 5th prime number will be less than 500).
Solution: Build a Sieve of Eratosthenes of size 10,001 * 100 = 1000100, generate a list of primes from the sieve and access the 10,000th element (since arrays start at zero). We already have a function for generating prime numbers up to n from our solution to problem 3.
<?php declare(strict_types=1); error_reporting(E_ALL); require_once __DIR__ . '/../primes.php'; $prime_count_target = 10001; // Assume at least 1 prime per 100 numbers $max_prime_candidate = $prime_count_target * 100; $primes = prime_numbers($max_prime_candidate); print($primes[$prime_count_target - 1] . "\n");