# 10001st prime

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:

```
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:

```
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:

```
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**