forked from CJEnright/Lucas-Lehmer
/
main.go
90 lines (73 loc) · 1.51 KB
/
main.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
package main
import (
"fmt"
"log"
"os"
"runtime"
"sync"
"time"
big "github.com/ncw/gmp"
// "github.com/cheggaaa/pb/v3"
)
var (
zero *big.Int = big.NewInt(0)
one *big.Int = big.NewInt(1)
two *big.Int = big.NewInt(2)
mu sync.Mutex
numWorkers = runtime.NumCPU()
// numWorkers = 1
currentP = uint(1)
)
const (
iterationsPerJob = 2048
)
func main() {
fmt.Println("Starting to look for primes")
fmt.Println("numWorkers:", numWorkers)
fmt.Println(time.Now())
file, err := os.OpenFile("logs.txt", os.O_APPEND|os.O_CREATE|os.O_WRONLY, 0666)
if err != nil {
log.Fatal(err)
}
log.SetOutput(file)
wg := &sync.WaitGroup{}
for i := 0; i < numWorkers; i++ {
wg.Add(1)
go spawnWorker()
}
wg.Wait()
}
func spawnWorker() {
for {
mu.Lock()
initialP := currentP
currentP += iterationsPerJob
mu.Unlock()
// bar := pb.StartNew(iterationsPerJob)
for i := uint(0); i < iterationsPerJob; i++ {
myP := initialP + i
if big.NewInt(int64(myP)).ProbablyPrime(4) && LucasLehmer(myP) {
fmt.Printf("2^%d-1 is prime\n", myP)
log.Println("2^", myP, "-1 is prime")
// fmt.Println(time.Now())
}
// bar.Increment()
}
}
}
func LucasLehmer(p uint) (isPrime bool) {
var dummy1, dummy2 big.Int
s := big.NewInt(4)
m := big.NewInt(0)
m = m.Sub(m.Lsh(one, p), one) // = (1 << p) - 1
for i := 0; i < int(p)-2; i++ {
s = s.Sub(s.Mul(s, s), two)
for s.Cmp(m) == 1 {
s.Add(dummy1.And(s, m), dummy2.Rsh(s, p))
}
if s.Cmp(m) == 0 {
s = zero
}
}
return s.Cmp(zero) == 0
}