-
Notifications
You must be signed in to change notification settings - Fork 0
/
is.go
94 lines (72 loc) · 1.81 KB
/
is.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
package prime
import (
"math"
"math/big"
)
// Is determines whether a given 64-bit number is prime.
func Is(n int64) bool {
if n >= int64(math.Sqrt(math.MaxInt64)) {
bigN := big.NewInt(n)
return BigIs(bigN)
}
if n <= 1 {
return false
}
if n <= 3 {
return true
}
if n%2 == 0 || n%3 == 0 {
return false
}
for i := int64(5); i*i <= n; i += 6 {
if n%i == 0 || n%(i+2) == 0 {
return false
}
}
return true
}
// BigIs determines whether a given number of arbitrary size is prime.
func BigIs(bigN *big.Int) bool {
if bigN.Cmp(bigOne) <= 0 {
return false
}
if bigN.Cmp(bigThree) <= 0 {
return true
}
bigTemp := new(big.Int)
if bigTemp.Mod(bigN, bigTwo).Cmp(bigZero) == 0 || bigTemp.Mod(bigN, bigThree).Cmp(bigZero) == 0 {
return false
}
for bigI := big.NewInt(5); bigTemp.Mul(bigI, bigI).Cmp(bigN) <= 0; bigI.Add(bigI, bigSix) {
if bigTemp.Mod(bigN, bigI).Cmp(bigZero) == 0 {
return false
}
bigTemp.Add(bigI, bigTwo)
if bigTemp.Mod(bigN, bigTemp).Cmp(bigZero) == 0 {
return false
}
}
return true
}
// IsAdditive determines whether a given 64-bit number is additively prime.
// This means that the number itself must be prime and the sum of
// its decimal digits must also be prime.
func IsAdditive(n int64) bool {
bigN := big.NewInt(n)
return BigIsAdditive(bigN)
}
// BigIsAdditive determines whether a given number of arbitrary size
// is additively prime.
// This means that the number itself must be prime and the sum of
// its decimal digits must also be prime.
func BigIsAdditive(bigN *big.Int) bool {
if !BigIs(bigN) {
return false
}
bigDigitSum := new(big.Int)
bigTemp := new(big.Int)
for bigI := (new(big.Int)).Set(bigN); bigI.Cmp(bigZero) > 0; bigI.Div(bigI, bigTen) {
bigDigitSum.Add(bigDigitSum, bigTemp.Mod(bigI, bigTen))
}
return BigIs(bigDigitSum)
}