Skip to content

Instantly share code, notes, and snippets.

@tylerkerr
Created June 18, 2017 18:55
Show Gist options
  • Save tylerkerr/fcd82c6651b52dac4911d912e8eb64b2 to your computer and use it in GitHub Desktop.
Save tylerkerr/fcd82c6651b52dac4911d912e8eb64b2 to your computer and use it in GitHub Desktop.
package main
import "fmt"
import "os"
import "strconv"
import "math"
func sieve(n int) []int {
isprime := make([]bool, n+1)
for i := range isprime { // help. how do i initialize the array as all true
isprime[i] = true
}
isprime[0] = false
if len(isprime) > 1 {
isprime[1] = false
}
max := int(math.Ceil(math.Sqrt(float64(n))))
for i := 2; i <= max; i++ {
if isprime[i] == true {
for j := i * i; j <= n; j += i {
isprime[j] = false
}
}
}
var primes []int
for i, v := range isprime {
if v == true {
primes = append(primes, i)
}
}
return primes
}
func main() {
nthprime, err := strconv.Atoi(os.Args[1] - 1)
if err != nil {
fmt.Println(err)
}
var searchbound int
var searchmultiplier float64
if nthprime == 1 {
searchbound = 2
} else {
if nthprime < 11 {
searchmultiplier = 3
} else {
searchmultiplier = 1.2408246135107 // found this via trial and error
}
searchbound = int(math.Log(float64(nthprime)) * float64(nthprime) * searchmultiplier)
}
primes := sieve(searchbound)
// efficiency := float64(nthprime) / float64(len(primes))
// fmt.Printf("searched up to %d and found %d primes (efficiency of %.4f). prime number %d is:\n", searchbound, len(primes), efficiency, nthprime)
fmt.Println(primes[nthprime])
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment