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 n by Erathostenes' method:

1. Create a list of consecutive integers from 2 … n (2,3,4,…,n)
2. Initially, let p equal 2, smallest prime.
3. 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)
4. 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
5. 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