-
Notifications
You must be signed in to change notification settings - Fork 7
/
prime.go
133 lines (113 loc) · 3.41 KB
/
prime.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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
// Package prime provides functionality to produce prime numbers using all
// available cpu cores. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
// can be an starting point to find more information about how to calculate
// prime numbers.
//
// The method used in Primes function is Segmented sieve. Segmenting will
// Reduce memory requirement of process.
// The space complexity of the algorithm is O(√n).
package prime
import (
"math"
"runtime"
"sync"
)
func fill(nums []bool, i uint64, max uint64) {
a := 3 * i
for a <= max {
nums[a/2] = true
a = a + 2*i
}
}
func goFill(nums []bool, i uint64, max uint64, next chan bool) {
fill(nums, i, max)
<-next
}
// SieveOfEratosthenes returns a slice of all prime numbers equal or lower than max using Sieve Of Eratosthenes.
// This is without segmenting.
func SieveOfEratosthenes(n uint64) []uint64 {
cores := runtime.NumCPU()
next := make(chan bool, cores)
var nums = make([]bool, n/2+1)
m := uint64(math.Sqrt(float64(n)))
for i := uint64(3); i <= m; i = i + 2 {
if nums[i/2] == false {
go goFill(nums, i, n, next)
next <- true
}
}
for i := 0; i < cores; i++ {
next <- true
}
var ps []uint64
if n >= 2 {
ps = append(ps, 2)
}
for i := uint64(3); i <= n; i = i + 2 {
if nums[i/2] == false {
ps = append(ps, i)
}
}
return ps
}
var csegPool sync.Pool
func fillSegments(n uint64, basePrimes []uint64, allPrimes *[]uint64, segSize uint64, segNum uint64, next chan bool, nextTurn []chan bool) {
cseg := (csegPool.Get()).([]bool)
for i := uint64(0); i < segSize; i++ {
cseg[i] = false
}
for i := 0; i < len(basePrimes); i++ {
jMax := segSize * (segNum + 1) / basePrimes[i]
for j := (segSize * segNum) / basePrimes[i]; j < jMax; j++ {
sn := (j + 1) * basePrimes[i]
cseg[sn-segSize*segNum-1] = true
}
}
// This waiting for turn is to avoid sorts at the end.
// Sorts are much more expensive than this wait even for a
// mostly sorted list.
if segNum > 1 {
<-nextTurn[segNum]
}
for i := uint64(0); i < segSize; i++ {
if !cseg[i] && segSize*segNum+i+1 <= n {
*allPrimes = append(*allPrimes, segSize*segNum+i+1)
}
}
<-next
if int(segNum)+1 < len(nextTurn) {
nextTurn[segNum+1] <- true
}
csegPool.Put(cseg)
}
// Primes is using Segmented sieve. This method will reduce memory usae of Sieve of Eratosthenes considerably.
// besides memory allocation for Prime numbers slice, there is only O(sqrt(n)) extra memory required for the operation
// You can learn more about it in https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
func Primes(n uint64) (allPrimes []uint64) {
if uint64(math.Log(float64(n))-1) == 0 {
return SieveOfEratosthenes(n)
}
// There is a function pi(x) in math that will returns approximate number of prime numbers below n.
allPrimes = make([]uint64, 0, n/uint64(math.Log(float64(n))-1))
segSize := uint64(math.Sqrt(float64(n)))
csegPool.New = func() interface{} {
return make([]bool, segSize)
}
basePrimes := SieveOfEratosthenes(segSize)
allPrimes = append(allPrimes, basePrimes...)
cores := runtime.NumCPU()
next := make(chan bool, cores)
var nextTurn []chan bool
nextTurn = make([]chan bool, n/segSize+1)
for i := uint64(0); i < n/segSize+1; i++ {
nextTurn[i] = make(chan bool)
}
for segNum := uint64(1); segNum <= n/segSize; segNum++ {
go fillSegments(n, basePrimes, &allPrimes, segSize, segNum, next, nextTurn)
next <- true
}
for i := 0; i < cores; i++ {
next <- true
}
return allPrimes
}