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 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.

erathostenes_sieve

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