-
Notifications
You must be signed in to change notification settings - Fork 0
/
euler007.go
68 lines (58 loc) · 1.27 KB
/
euler007.go
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//usr/bin/env go run $0 $@ ; exit
package main
import (
"fmt"
"math"
)
var prime_table []bool
var table_size int = 1000
func isPrime(n int) bool {
if n < table_size {
return prime_table[n]
}
search_limit := int(math.Sqrt(float64(n)))
if n <= search_limit {
panic(n)
}
for i := 0; i < table_size; i++ {
if prime_table[i] == false {
continue
}
if n % i == 0 {
return false
}
}
return true
}
func main() {
prime_table = make([]bool, table_size)
// build sieve of Eratosthenes
prime_table[0] = false
prime_table[1] = false
prime_table[2] = true
prime_table[3] = true
for n := 5; n < table_size; n++ {
prime_table[n] = true
}
for n := 3; n < table_size; n++ {
if n & 1 == 0 {
prime_table[n] = false
} else {
if prime_table[n] == true {
for m := 2; m * n < table_size; m++ {
prime_table[m * n] = false
}
}
}
}
prime_cnt := 0
for n := 1; true ; n++ {
if isPrime(n) {
prime_cnt ++
if prime_cnt == 10001 {
fmt.Println(n)
break
}
}
}
}