-
Notifications
You must be signed in to change notification settings - Fork 7
/
primes_BM.c
121 lines (113 loc) · 4.56 KB
/
primes_BM.c
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
// file primes_BM.c
// SPDX-License-Identifier: GPL-3.0-or-later
/***
BISMON
Copyright © 2018 CEA (Commissariat à l'énergie atomique et aux énergies alternatives)
contributed by Basile Starynkevitch (working at CEA, LIST, France)
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
***/
#include "bismon.h"
// an array of primes, gotten with something similar to
// /usr/games/primes 3 | awk '($1>p+p/9){print $1, ","; p=$1}'
static const int64_t primes_tab_BM[] = {
3, 5, 7, 11, 13, 17, 19, 23, 29, 37, 43, 53, 59, 67, 79, 89, 101, 113,
127, 149, 167, 191, 223, 251, 281, 313, 349, 389, 433, 487, 547, 613,
683, 761, 853, 953, 1061, 1181, 1319, 1471, 1637, 1823, 2027, 2267,
2521, 2803, 3119, 3467, 3853, 4283, 4759, 5297, 5897, 6553, 7283, 8093,
8999, 10007, 11119, 12373, 13751, 15287, 16987, 18899, 21001, 23339,
25933, 28817, 32027, 35591, 39551, 43951, 48847, 54277, 60317, 67021,
74471, 82757, 91957, 102181, 113537, 126173, 140197, 155777, 173087,
192319, 213713, 237467, 263863, 293201, 325781, 361979, 402221, 446921,
496579, 551767, 613097, 681221, 756919, 841063, 934517, 1038383, 1153759,
1281961, 1424407, 1582697, 1758553, 1953949, 2171077, 2412323, 2680367,
2978189, 3309107, 3676789, 4085339, 4539277, 5043653, 5604073, 6226757,
6918619, 7687387, 8541551, 9490631, 10545167, 11716879, 13018757,
14465291, 16072547, 17858389, 19842659, 22047401, 24497113, 27219019,
30243359, 33603743, 37337497, 41486111, 46095719, 51217477, 56908337,
63231499, 70257241, 78063641, 86737379, 96374881, 107083213, 118981367,
132201521, 146890631, 163211821, 181346479, 201496157, 223884629,
248760703, 276400823, 307112027, 341235667, 379150777, 421278643,
468087391, 520097111, 577885681, 642095213, 713439127, 792710159,
880789067, 978654533, 1087393949, 1208215531, 1342461719, 1491624137,
1657360153, 1841511311, 2046123679, 2273470799, 2526078691, 2806754123,
3118615693, 3465128567, 3850142869, 4277936557, 4753262879, 5281403287,
5868225889, 6520251019, 7244723357, 8049692639, 8944102939, 9937892189,
11042102507, 12269002787, 13632225331, 15146917109, 16829907907,
18699897683, 20777664097, 23086293457, 25651437191, 28501596883,
31668440987, 35187156661, 39096840751, 43440934181, 48267704657,
53630782993, 59589758903, 66210843271, 73567603643, 81741781829,
90824202037, 100915780061, 112128644521, 124587382807, 138430425373,
153811583771, 170901759761, 189890844179, 210989826869, 234433140979,
260481267763, 289423630891, 321581812103, 357313124579, 397014582917,
441127314403, 490141460453, 544601622727, 605112914149, 672347682449,
747052980503, 830058867229, 922287630259, 1024764033637, 1138626704071,
};
int64_t
prime_above_BM (int64_t n)
{
unsigned numprimes = sizeof (primes_tab_BM) / sizeof (primes_tab_BM[0]);
int lo = 0, hi = numprimes;
if (n >= primes_tab_BM[numprimes - 1])
return 0;
if (n < 2)
return 2;
while (lo + 6 < hi)
{
int md = (lo + hi) / 2;
if (primes_tab_BM[md] > n)
hi = md;
else
lo = md;
};
if (hi < (int) numprimes - 1)
hi++;
if (hi < (int) numprimes - 1)
hi++;
for (int ix = lo; ix < hi; ix++)
if (primes_tab_BM[ix] > n)
return primes_tab_BM[ix];
return 0;
}
int64_t
prime_below_BM (int64_t n)
{
unsigned numprimes = sizeof (primes_tab_BM) / sizeof (primes_tab_BM[0]);
int lo = 0, hi = numprimes;
if (n >= primes_tab_BM[numprimes - 1])
return 0;
if (n < 2)
return 2;
while (lo + 6 < hi)
{
int md = (lo + hi) / 2;
if (primes_tab_BM[md] > n)
hi = md;
else
lo = md;
};
if (hi < (int) numprimes - 1)
hi++;
if (hi < (int) numprimes - 1)
hi++;
for (int ix = hi; ix >= 0; ix--)
if (primes_tab_BM[ix] < n)
return primes_tab_BM[ix];
return 0;
}
/****************
** for Emacs...
** Local Variables: ;;
** compile-command: "./Build" ;;
** End: ;;
****************/
// eof primes_BM.c