/
primes.go
63 lines (51 loc) · 1.19 KB
/
primes.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
package projecteuler
import (
"math"
)
// Primes calculates and returns slice of primes smaller than limit, or until f returns true
func Primes(limit int, f func(...interface{}) bool, args ...interface{}) (primes []int) {
primes = append(primes, 2)
primes = append(primes, 3)
var i, num, numRootLimit int
for num = 5; num < limit; num += 2 {
numRootLimit = int(math.Sqrt(float64(num)))
for i = 0; primes[i] <= numRootLimit; i++ {
if num%primes[i] == 0 {
break
}
}
if primes[i] > numRootLimit {
primes = append(primes, num)
if f != nil {
args = append(args, num)
if f(args...) {
break
}
args = args[:len(args)-1]
}
}
}
return
}
// PrimeSet calculates and returns slice of primes less than limit and puts them in primeSet
func PrimeSet(limit int) (primes []int, primeSet map[int]struct{}) {
primes = Primes(limit, nil)
primeSet = make(map[int]struct{})
for _, x := range primes {
primeSet[x] = struct{}{}
}
return
}
// IsPrime returns true iff x is prime
func IsPrime(x int64) bool {
if x%2 == 0 {
return false
}
root := int64(math.Sqrt(float64(x)))
for i := int64(3); i <= root; i += 2 {
if x%i == 0 {
return false
}
}
return true
}