[Golang] 10001st Prime - Problem 7 - Project Euler

Go solution to 10001st prime - Problem 7 - Project Euler. [1]

Problem:

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?

Solution:

According to prime number theorem, the 10001st prime number is probably located at somewhere around 1,000,000. We use Sieve of Eratosthenes [2] to find all prime numbers under 1,100,000. The number of primes is 10,453, and the 10001st prime is 104743.

Run Code on Go Playground

package main

import (
      "fmt"
)

func SieveOfEratosthenes(n int) []int {
      // Create a boolean array "prime[0..n]" and initialize
      // all entries it as true. A value in prime[i] will
      // finally be false if i is Not a prime, else true.
      integers := make([]bool, n+1)
      for i := 2; i < n+1; i++ {
              integers[i] = true
      }

      for p := 2; p*p <= n; p++ {
              // If integers[p] is not changed, then it is a prime
              if integers[p] == true {
                      // Update all multiples of p
                      for i := p * 2; i <= n; i += p {
                              integers[i] = false
                      }
              }
      }

      // return all prime numbers <= n
      var primes []int
      for p := 2; p <= n; p++ {
              if integers[p] == true {
                      primes = append(primes, p)
              }
      }

      return primes
}

func main() {
      primes := SieveOfEratosthenes(110000)
      fmt.Println(len(primes))
      if len(primes) > 10001 {
              fmt.Println(primes[10000])
      }
}

Tested on: Go Playground

References:

[1]	10001st prime - Problem 7 - Project Euler

[2]	[Golang] Sieve of Eratosthenes