## oschvr

### a blog about software, cloud computing, security, money, business, travelling and life.

**← Problems**

# 10001st prime

#### 1 min

#### over 1 year ago

###### 12/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:

```
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))
}
```

Execution time: 194ns

Answe
10,001th Prime: **104743**