Project Euler - 007

icymirror

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個(gè)素?cái)?shù)：2, 3, 5, 7, 11, 13, 我們可以發(fā)現(xiàn)第六個(gè)素?cái)?shù)是13.
那么，第10001個(gè)素?cái)?shù)是多少？

代碼：

1. 
   
2. package main
   
3. 
   
4. import (
   
5.         "fmt"
   
6.         "math"
   
7. )
   
8. 
   
9. func VerifyPrimeWithExistingPrimeList(number int, primes []int) bool {
   
10.         if number < 2 {
    
11.                 return false
    
12.         }
    
13. 
    
14.         isPrime := true
    
15.         root := int(math.Sqrt(float64(number)))
    
16. 
    
17.         for _, factor := range primes {
    
18.                 if factor > root {
    
19.                         break
    
20.                 }
    
21. 
    
22.                 if (number % factor == 0){
    
23.                         isPrime = false
    
24.                         break
    
25.                 }
    
26.         }
    
27.        
    
28.         return isPrime
    
29. }
    
30. 
    
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.                 }
    
48. 
    
49.                 primes = append(primes, base)
    
50.                 base += 2
    
51.         }
    
52. 
    
53.         return primes
    
54. }
    
55. 
    
56. func Problem007(turn int) int {
    
57.         primes := BuildPrimeTable(turn)
    
58.         return primes[len(primes) - 1]
    
59. }
    
60. 
    
61. func main() {
    
62.         fmt.Println("Problem 007 result: ", Problem007(10001))
    
63. }
    

復(fù)制代碼