blob: 195215bee0ab0d91f55ef1f2d9a0c5482a85601b (
plain)
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
#include <gu/defs.h>
#include <gu/assert.h>
static const uint32_t gu_prime_wheel_mask = 0UL
| 1 << 1
| 1 << 7
| 1 << 11
| 1 << 13
| 1 << 17
| 1 << 19
| 1 << 23
| 1 << 29;
static bool
gu_prime_wheel(int i)
{
gu_assert(i >= 0 && i < 30);
return !!(gu_prime_wheel_mask & (1 << i));
}
static const uint32_t gu_small_prime_mask = 0UL
| 1 << 2
| 1 << 3
| 1 << 5
| 1 << 7
| 1 << 11
| 1 << 13
| 1 << 17
| 1 << 19
| 1 << 23
| 1 << 29
| 1U << 31;
static bool
gu_is_wheel_prime(int u)
{
gu_assert(u > 30 && u % 2 != 0 && u % 3 != 0 && u % 5 != 0);
int d = 0;
int i = 7;
goto start;
while (d * d <= u) {
for (i = 1; i <= 29; i+=2) {
start:
if (gu_prime_wheel(i) && u % (d + i) == 0) {
return false;
}
}
d += 30;
}
return true;
}
GU_INTERNAL int
gu_prime_inf(int i)
{
if (i < 2) {
return 0;
} else if (i < 32) {
while (!(gu_small_prime_mask & (1 << i))) {
i--;
}
return i;
}
int d = (i - 1) | 1;
int r = d % 30;
while (!gu_prime_wheel(r) || !gu_is_wheel_prime(d)) {
d -= 2;
r -= 2;
if (r < 0) {
r += 30;
}
}
return d;
}
GU_INTERNAL int
gu_prime_sup(int i)
{
if (i <= 2) {
return 2;
} else if (i < 32) {
while (!(gu_small_prime_mask & (1 << i))) {
i++;
}
return i;
}
int d = i | 1;
int r = d % 30;
while (!gu_prime_wheel(r) || !gu_is_wheel_prime(d)) {
d += 2;
r += 2;
if (r > 30) {
r -= 30;
}
}
return d;
}
GU_INTERNAL bool
gu_is_prime(int i)
{
if (i < 2) {
return false;
} else if (i < 30) {
return !!(gu_small_prime_mask & (1 << i));
} else if (!gu_prime_wheel(i % 30)) {
return false;
} else {
return gu_is_wheel_prime(i);
}
}
GU_INTERNAL bool
gu_is_twin_prime(int i)
{
return gu_is_prime(i) && gu_is_prime(i - 2);
}
GU_INTERNAL int
gu_twin_prime_inf(int i)
{
while (true) {
i = gu_prime_inf(i);
if (i == 0) {
return 0;
} else if (gu_is_prime(i - 2)) {
return i;
}
i = i - 4;
}
return i;
}
GU_INTERNAL int
gu_twin_prime_sup(int i)
{
if (i <= 5) {
return 5;
}
i = i - 2;
while (true) {
i = gu_prime_sup(i);
if (gu_is_prime(i + 2)) {
return i + 2;
}
i = i + 4;
}
return i;
}
|
