## oschvr

### a blog about software, programming, business, travelling and life.

**← Problems**

# 10001st prime

#### 20 days ago

###### 06/05/2019

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

At first glance, a simple iteration whilst checking if index position is prime, would suffice.

A *pseudocode* attempt:

`1 2 3 4 5 6 7 8 9`

`sum = 0 for i = 2; i <= ?; i++ { if(isPrime(i)){ sum++ if ( sum >= 10001) { return i } } }`

Using the solution in **go** to check if is prime from former examples:

`1 2 3 4 5 6 7 8 9`

`func isPrime(x int64) bool { var i int64 = 2 for ; i < x; i++ { if x%i == 0 { return false } } return true }`

The solution would scale to

$$O(n^2)$$.

This is not viable. Also, there's no upper bound to set our iteration limit, meaning, we don't know up to which number we should iterate to find the **10,001 prime**.

So digging further, I found about the **Erathostenes Sieve**:

An ancient algorithm for finding all prime numbers up to any given limit

This is exactly what we need. Let's look at the procedure:

To find all the prime numbers less than or equal to a given integer

nby Erathostenes' method:

- Create a list of consecutive integers from 2 ... n (2,3,4,...,
*n*) - Initially, let
*p*equal 2, smallest prime. - Enumerate multiples of
*p*by counting in increments of p from*2p*to*n*, and mark them in the list (these will be*2p, 3p, 4p, ...;*the*p*itself should not be marked) - Find the first number greater than
*p*in the list that is not marked, if there is not such number, stop. Otherwise, let*p*now equal to this number (which is next prime), and repeat step 3 - When algorithm terminates, the numbers remain not marked in the list, are all primes below n.

Here's the code I came up:

`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52`

`package main import ( "fmt" "math" "time" ) func primeSieve(n, limit int) int { // Create and populate array of values // lim := c a := make([]bool, limit+1) for i := 0; i < limit+1; i++ { a[i] = true } // Start with 2 // p * p <= limit === p <= int(math.Sqrt(float64(limit))) for p := 2; p <= int(math.Sqrt(float64(limit))); p++ { // At first all will be true if a[p] == true { // i = 2 * 2, i = 3 * 2, i = 4 * 2, ..., i = i * i // Calculate multiples of 2, then 3, then 5, then 7 for i := p * 2; i <= limit; i += p { a[i] = false } } } // Count primes up to n // if primes == 10001, return sievePrime var primes, sievePrime int for p := 2; p <= limit; p++ { if a[p] == true { primes++ // Sum up primes and print 10,001th prime if primes <= n { sievePrime = p } } } return sievePrime } func main() { start := time.Now() // Nth prime to find var n, limit int = 10001, 105000 // Arbitrary limit find by testing fmt.Println("Execution time: ", time.Since(start)) fmt.Println("10,001th Prime: ", primeSieve(n, limit)) }`

### Answer

Execution time: 194ns

10,001th Prime: **104743**