Chinaunix

标题: Project Euler - 007 [打印本页]
作者: icymirror    时间: 2015-09-27 12:46
标题: Project Euler - 007
Problem 007:
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?

问题7：
通过列出前6个素数：2, 3, 5, 7, 11, 13, 我们可以发现第六个素数是13.
那么，第10001个素数是多少？

代码：

  2. package main

  4. import (
  5.         "fmt"
  6.         "math"
  7. )

  9. func VerifyPrimeWithExistingPrimeList(number int, primes []int) bool {
  10.         if number < 2 {
  11.                 return false
  12.         }

  14.         isPrime := true
  15.         root := int(math.Sqrt(float64(number)))

  17.         for _, factor := range primes {
  18.                 if factor > root {
  19.                         break
  20.                 }

  22.                 if (number % factor == 0){
  23.                         isPrime = false
  24.                         break
  25.                 }
  26.         }
  27.        
  28.         return isPrime
  29. }

  31. func BuildPrimeTable(count int) []int {
  32.         primes := make([]int, 1)
  33.         if count < 1 {
  34.                 return primes
  35.         }
  36.         primes[0] = 2
  37.        
  38.         base := 3
  39.         for check := 0; check < count - 1; check++ {
  40.                 for {
  41.                         if (VerifyPrimeWithExistingPrimeList(base, primes) == false) {
  42.                                 base += 2
  43.                                 continue
  44.                         } else {
  45.                                 break
  46.                         }
  47.                 }

  49.                 primes = append(primes, base)
  50.                 base += 2
  51.         }

  53.         return primes
  54. }

  56. func Problem007(turn int) int {
  57.         primes := BuildPrimeTable(turn)
  58.         return primes[len(primes) - 1]
  59. }

  61. func main() {
  62.         fmt.Println("Problem 007 result: ", Problem007(10001))
  63. }
复制代码




欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2