Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
primes.C
Go to the documentation of this file.
1
2/*
3 Aleph_w
4
5 Data structures & Algorithms
6 version 2.0.0b
7 https://github.com/lrleon/Aleph-w
8
9 This file is part of Aleph-w library
10
11 Copyright (c) 2002-2026 Leandro Rabindranath Leon
12
13 Permission is hereby granted, free of charge, to any person obtaining a copy
14 of this software and associated documentation files (the "Software"), to deal
15 in the Software without restriction, including without limitation the rights
16 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
17 copies of the Software, and to permit persons to whom the Software is
18 furnished to do so, subject to the following conditions:
19
20 The above copyright notice and this permission notice shall be included in all
21 copies or substantial portions of the Software.
22
23 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
24 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
25 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
26 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
28 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
29 SOFTWARE.
30*/
31
32
33# include <exception>
34# include <string>
35# include <algorithm>
36
37# include <ah-errors.H>
38# include <primes.H>
39
40namespace Primes
41{
42
43 // list of primes, from ~100 to ~4e9 with increasing step sizes
44
45 const unsigned long primeList[] =
46 {
47 101, 211, 307, 401, 503, 601, 701, 809, 907, 1009,
48 1103, 1201, 1301, 1409, 1511, 1601, 1709, 1801, 1901, 2003,
49 2111, 2203, 2309, 2411, 2503, 2609, 2707, 2801, 2903, 3001,
50 3109, 3203, 3301, 3407, 3511, 3607, 3701, 3803, 3907, 4001,
51 4111, 4201, 4327, 4409, 4507, 4603, 4703, 4801, 4903, 5003,
52 5101, 5209, 5303, 5407, 5501, 5623, 5701, 5801, 5903, 6007,
53 6101, 6203, 6301, 6421, 6521, 6607, 6701, 6803, 6907, 7001,
54 7103, 7207, 7307, 7411, 7507, 7603, 7703, 7817, 7901, 8009,
55 8101, 8209, 8311, 8419, 8501, 8609, 8707, 8803, 8923, 9001,
56 9103, 9203, 9311, 9403, 9511, 9601, 9719, 9803, 9901, 10007,
57 10103, 10211, 10301, 10427, 10501, 10601, 10709, 10831, 10903, 11003,
58 11113, 11213, 11311, 11411, 11503, 11617, 11701, 11801, 11903, 12007,
59 12101, 12203, 12301, 12401, 12503, 12601, 12703, 12809, 12907, 13001,
60 13103, 13217, 13309, 13411, 13513, 13613, 13709, 13807, 13901, 14009,
61 14107, 14207, 14303, 14401, 14503, 14621, 14713, 14813, 14923, 15013,
62 15101, 15217, 15307, 15401, 15511, 15601, 15727, 15803, 15901, 16001,
63 16103, 16217, 16301, 16411, 16519, 16603, 16703, 16811, 16901, 17011,
64 17107, 17203, 17317, 17401, 17509, 17609, 17707, 17807, 17903, 18013,
65 18119, 18211, 18301, 18401, 18503, 18617, 18701, 18803, 18911, 19001,
66 19121, 19207, 19301, 19403, 19501, 19603, 19709, 19801, 19913, 20011,
67 20101, 20201, 20323, 20407, 20507, 20611, 20707, 20807, 20903, 21001,
68 21101, 21211, 21313, 21401, 21503, 21601, 21701, 21803, 21911, 22003,
69 22109, 22229, 22303, 22409, 22501, 22613, 22709, 22807, 22901, 23003,
70 23117, 23201, 23311, 23417, 23509, 23603, 23719, 23801, 23909, 24001,
71 24103, 24203, 24317, 24407, 24509, 24611, 24709, 24809, 24907, 25013,
72 25111, 25219, 25301, 25409, 25523, 25601, 25703, 25801, 25903, 26003,
73 26107, 26203, 26309, 26407, 26501, 26627, 26701, 26801, 26903, 27011,
74 27103, 27211, 27329, 27407, 27509, 27611, 27701, 27803, 27901, 28001,
75 28109, 28201, 28307, 28403, 28513, 28603, 28703, 28807, 28901, 29009,
76 29101, 29201, 29303, 29401, 29501, 29611, 29717, 29803, 29917, 30011,
77 30103, 30203, 30307, 30403, 30509, 30631, 30703, 30803, 30911, 31013,
78 31121, 31219, 31307, 31469, 31511, 31601, 31721, 31817, 31907, 32003,
79 32117, 32203, 32303, 32401, 32503, 32603, 32707, 32801, 32909, 33013,
80 33107, 33203, 33301, 33403, 33503, 33601, 33703, 33809, 33911, 34019,
81 34123, 34211, 34301, 34403, 34501, 34603, 34703, 34807, 34913, 35023,
82 35107, 35201, 35311, 35401, 35507, 35603, 35729, 35801, 35911, 36007,
83 36107, 36209, 36307, 36433, 36523, 36607, 36709, 36809, 36901, 37003,
84 37117, 37201, 37307, 37409, 37501, 37607, 37717, 37811, 37907, 38011,
85 38113, 38201, 38303, 38431, 38501, 38603, 38707, 38803, 38903, 39019,
86 39103, 39209, 39301, 39409, 39503, 39607, 39703, 39821, 39901, 40009,
87 40111, 40213, 40343, 40423, 40507, 40609, 40709, 40801, 40903, 41011,
88 41113, 41201, 41333, 41411, 41507, 41603, 41719, 41801, 41903, 42013,
89 42101, 42209, 42307, 42403, 42509, 42611, 42701, 42821, 42901, 43003,
90 43103, 43201, 43313, 43403, 43517, 43607, 43711, 43801, 43913, 44017,
91 44101, 44201, 45007, 46021, 47017, 48017, 49003, 50021, 51001, 52009,
92 53003, 54001, 55001, 56003, 57037, 58013, 59009, 60013, 61001, 62003,
93 63029, 64007, 65003, 66029, 67003, 68023, 69001, 70001, 71011, 72019,
94 73009, 74017, 75011, 76001, 77003, 78007, 79031, 80021, 81001, 82003,
95 83003, 84011, 85009, 86011, 87011, 88001, 89003, 90001, 91009, 92003,
96 93001, 94007, 95003, 96001, 97001, 98009, 99013, 100003, 106013, 107021,
97 108007, 109001, 110017, 111029, 112019, 113011, 114001, 115001, 116009, 117017,
98 118033, 119027, 120011, 121001, 122011, 123001, 124001, 125003, 126001, 127031,
99 128021, 129001, 130003, 131009, 132001, 133013, 134033, 135007, 136013, 137029,
100 138007, 139021, 140009, 141023, 142007, 143053, 144013, 145007, 146009, 147011,
101 148013, 149011, 150001, 151007, 152003, 153001, 154001, 155003, 156007, 157007,
102 158003, 159013, 160001, 161009, 162007, 163003, 164011, 165001, 166013, 167009,
103 168013, 169003, 170003, 171007, 172001, 173021, 174007, 175003, 176017, 177007,
104 178001, 179021, 180001, 181001, 182009, 183023, 184003, 185021, 186007, 187003,
105 188011, 189011, 190027, 191021, 192007, 193003, 194003, 195023, 196003, 197003,
106 198013, 199021, 200003, 201007, 202001, 203011, 204007, 205019, 206009, 207013,
107 208001, 209021, 210011, 211007, 212029, 213019, 214003, 215051, 216023, 217001,
108 218003, 219001, 220009, 221021, 222007, 223007, 224011, 225023, 226001, 227011,
109 228013, 229003, 230003, 244003, 249017, 254003, 259001, 264007, 269023, 274007,
110 279001, 284003, 289001, 294001, 299011, 304009, 309007, 314003, 319001, 324011,
111 329009, 334021, 339023, 344017, 349007, 354001, 359003, 364027, 369007, 374009,
112 379007, 384001, 389003, 394007, 399023, 404009, 409007, 414013, 419047, 424001,
113 429007, 434009, 439007, 444001, 449003, 454009, 459007, 464003, 469009, 474017,
114 479023, 484019, 489001, 494023, 499021, 504001, 509023, 514001, 519011, 524047,
115 529003, 534007, 539003, 544001, 549001, 554003, 559001, 564013, 569003, 574003,
116 579011, 584011, 589021, 594023, 599003, 604001, 609043, 614041, 619007, 624007,
117 629003, 634003, 639007, 644009, 649001, 654001, 659011, 664009, 669023, 674017,
118 679033, 684007, 689021, 694019, 699001, 704003, 709043, 714029, 719009, 724001,
119 729019, 734003, 739003, 744019, 749011, 754003, 759001, 764003, 769003, 774001,
120 779003, 784009, 789001, 794009, 799003, 804007, 809023, 814003, 819001, 824017,
121 829001, 834007, 839009, 844001, 849019, 854017, 859003, 864007, 869017, 874001,
122 879001, 884003, 889001, 894011, 899009, 904019, 909019, 914021, 919013, 924019,
123 929003, 934001, 939007, 944003, 949001, 954001, 959009, 964009, 969011, 974003,
124 979001, 984007, 989011, 994013, 999007, 1004027, 1009007, 1014007, 1019023, 1024021,
125 1029001, 1034003, 1039001, 1044019, 1049011, 1054003, 1059001, 1064017, 1069001, 1074001,
126 1079009, 1084001, 1089017, 1094011, 1099031, 1104017, 1109021, 1114019, 1119029, 1124027,
127 1129013, 1134031, 1139003, 1144001, 1149007, 1154017, 1159001, 1164001, 1169009, 1174021,
128 1179011, 1184003, 1189003, 1194019, 1199039, 1204003, 1209007, 1214011, 1219003, 1224029,
129 1229021, 1234001, 1239001, 1244003, 1249013, 1254013, 1259017, 1264009, 1269001, 1274011,
130 1279001, 1284007, 1289003, 1294019, 1299007, 1304003, 1309013, 1314011, 1319023, 1324007,
131 1329011, 1334057, 1339001, 1344011, 1349003, 1354007, 1359023, 1364009, 1369009, 1374007,
132 1379003, 1384013, 1389001, 1394009, 1399003, 1404059, 1409017, 1414001, 1419001, 1424021,
133 1429027, 1434011, 1439017, 1444007, 1449001, 1454003, 1459027, 1464011, 1469047, 1474003,
134 1479007, 1484009, 1489003, 1494019, 1499011, 1504033, 1509019, 1514027, 1519039, 1524007,
135 1529009, 1534019, 1539011, 1544003, 1549003, 1554019, 1559017, 1564001, 1569011, 1574003,
136 1579001, 1584001, 1589017, 1594027, 1599023, 1604003, 1609009, 1614001, 1619021, 1624009,
137 1629007, 1634011, 1639019, 1644001, 1649003, 1654013, 1659011, 1664009, 1669027, 1674011,
138 1679009, 1684019, 1689031, 1694023, 1699001, 1704023, 1709009, 1714003, 1719001, 1724027,
139 1729001, 1734011, 1739009, 1744007, 1749001, 1754033, 1759003, 1764001, 1769017, 1774007,
140 1779007, 1784021, 1789001, 1794007, 1799003, 1804007, 1809029, 1814003, 1819007, 1824001,
141 1829011, 1834031, 1839001, 1844021, 1849013, 1854011, 1859009, 1864001, 1869029, 1874003,
142 1879049, 1884007, 1889009, 1894001, 1899017, 1904011, 1909003, 1914001, 1919009, 1924003,
143 1929043, 1934021, 1939009, 1944011, 1949023, 1954003, 1959011, 1964009, 1969001, 1974029,
144 1979039, 1984007, 1989007, 1994033, 1999007, 2004001, 2009011, 2014009, 2019001, 2024063,
145 2029003, 2034017, 2039027, 2044013, 2049041, 2054009, 2059009, 2064031, 2069009, 2074031,
146 2079013, 2084003, 2089001, 2094011, 2099017, 2104013, 2109011, 2114003, 2119031, 2124007,
147 2129003, 2134003, 2139013, 2144011, 2149003, 2154007, 2159023, 2164003, 2169007, 2174017,
148 2179007, 2184001, 2189017, 2194013, 2199061, 2204003, 2209001, 2214001, 2219023, 2224009,
149 2229037, 2234009, 2239001, 2244091, 2249053, 2254033, 2259029, 2264027, 2269009, 2274007,
150 2279009, 2284003, 2289013, 2294009, 2299001, 2304011, 2309003, 2314003, 2319013, 2324017,
151 2329027, 2334001, 2339011, 2344019, 2349001, 2354039, 2359001, 2364001, 2369033, 2374007,
152 2379001, 2384017, 2389001, 2394017, 2399011, 2404009, 2409023, 2414021, 2419007, 2424017,
153 2429023, 2434001, 2439013, 2444017, 2449001, 2454007, 2459003, 2464003, 2469011, 2474039,
154 2479013, 2484011, 2489017, 2494031, 2499023, 2504009, 2509027, 2514013, 2519003, 2524003,
155 2529013, 2534009, 2539049, 2544011, 2549003, 2554003, 2559013, 2564011, 2569003, 2574007,
156 2579009, 2584007, 2589007, 2594003, 2599013, 2604011, 2609021, 2614043, 2619007, 2624023,
157 2629001, 2634001, 2639041, 2644003, 2649001, 2654011, 2659001, 2664001, 2669003, 2674013,
158 2679031, 2684021, 2689007, 2694001, 2699009, 2704019, 2709019, 2714009, 2719001, 2724013,
159 2729003, 2734007, 2739013, 2744003, 2749007, 2754001, 2759023, 2764001, 2769001, 2774011,
160 2779001, 2784007, 2789011, 2794003, 2799001, 2804023, 2809007, 2814001, 2819009, 2824021,
161 2829007, 2834011, 2839007, 2844013, 2849009, 2854003, 2859001, 2864021, 2869001, 2874007,
162 2879003, 2884051, 2889001, 2894041, 2899009, 2904001, 2909003, 2914001, 2919011, 2924021,
163 2929007, 2934059, 2939023, 2944003, 2949013, 2954023, 2959031, 2964011, 2969003, 2974001,
164 2979013, 2984039, 2989003, 2994031, 2999041, 3004013, 3009023, 3014003, 3019019, 3024013,
165 3029017, 3034013, 3039011, 3044017, 3049003, 3054001, 3059003, 3064013, 3069007, 3074009,
166 3079003, 3084013, 3089027, 3094027, 3099011, 3104063, 3109031, 3114019, 3119009, 3124001,
167 3129011, 3134017, 3139007, 3144007, 3149009, 3154001, 3159001, 3164003, 3169007, 3174001,
168 3179027, 3184003, 3189007, 3194017, 3199013, 3204011, 3209009, 3214007, 3219019, 3224009,
169 3229001, 3234017, 3239003, 3244001, 3249013, 3254023, 3259001, 3264007, 3269009, 3274001,
170 3279007, 3284003, 3289001, 3294007, 3299017, 3304003, 3309001, 3314009, 3319003, 3324017,
171 3329003, 3334049, 3339019, 3344021, 3349001, 3354007, 3359011, 3364037, 3369001, 3374017,
172 3379001, 3384049, 3389003, 3394031, 3399001, 3404033, 3409019, 3414001, 3419027, 3424019,
173 3429007, 3434047, 3439001, 3444017, 3449003, 3454013, 3459017, 3464003, 3469013, 3474047,
174 3479017, 3484001, 3489001, 3494009, 3499019, 3504001, 3509017, 3514013, 3519013, 3524029,
175 3529037, 3534017, 3539021, 3544027, 3549011, 3554011, 3559009, 3564017, 3569003, 3574013,
176 3579071, 3584011, 3589031, 3594001, 3599009, 3604019, 3609007, 3614003, 3619013, 3624001,
177 3629027, 3634009, 3639017, 3644021, 3649001, 3654017, 3659009, 3664013, 3669007, 3674003,
178 3679003, 3684011, 3689009, 3694013, 3699011, 3704003, 3709007, 3714013, 3719011, 3724001,
179 3729007, 3734039, 3739009, 3744001, 3749021, 3754019, 3759001, 3764003, 3769027, 3774013,
180 3779003, 3784003, 3789013, 3794003, 3799013, 3804011, 3809051, 3814009, 3819007, 3824017,
181 3829079, 3834013, 3839023, 3844019, 3849017, 3854003, 3859003, 3864019, 3869009, 3874009,
182 3879023, 3884011, 3889007, 3894001, 3899011, 3904001, 3909019, 3914003, 3919007, 3924017,
183 3929011, 3934001, 3939031, 3944009, 3949003, 3954001, 3959003, 3964007, 3969001, 3974023,
184 3979013, 3984031, 3989003, 3994007, 3999001, 4004009, 4009001, 4014001, 4019003, 4024001,
185 4029001, 4034011, 4039019, 4044013, 4049029, 4054009, 4059037, 4064023, 4069003, 4074011,
186 4079003, 4084001, 4089011, 4094003, 4099001, 4104007, 4109003, 4114003, 4119007, 4124009,
187 4129003, 4134023, 4139029, 4144001, 4149007, 4154009, 4159007, 4164007, 4169057, 4174013,
188 4179001, 4184017, 4189001, 4194007, 4199003, 4204001, 4209011, 4214003, 4219001, 4224037,
189 4229003, 4234007, 4239013, 4244003, 4249067, 4254007, 4259053, 4264021, 4269019, 4274003,
190 4279007, 4284011, 4289011, 4294039, 4299007, 4304011, 4309001, 4314017, 4319017, 4324003,
191 4329011, 4334003, 4339021, 4344007, 4349011, 4354001, 4359001, 4364011, 4369021, 4374001,
192 4379003, 4384013, 4389017, 4394021, 4399001, 4404019, 4409003, 4414001, 4419011, 4424009,
193 4429031, 4434019, 4439003, 4444001, 4449017, 4454003, 4459001, 4464007, 4469027, 4474027,
194 4479001, 4484021, 4489007, 4494019, 4499003, 4504009, 4509013, 4514023, 4519007, 4524007,
195 4529003, 4534007, 4539011, 4544009, 4549003, 4554007, 4559021, 4564013, 4569001, 4574027,
196 4579007, 4584031, 4589017, 4594001, 4599019, 4604063, 4609009, 4614031, 4619009, 4624003,
197 4629007, 4634009, 4639003, 4644001, 4649017, 4654009, 4659013, 4664003, 4669009, 4674023,
198 4679009, 4684003, 4689017, 4694003, 4699003, 4704013, 4709009, 4714067, 4719007, 4724047,
199 4729033, 4734017, 4739017, 4744001, 4749013, 4754011, 4759003, 4764037, 4769047, 4774001,
200 4779029, 4784009, 4789003, 4794001, 4799021, 4804021, 4809017, 4814027, 4819021, 4824011,
201 4829009, 4834021, 4839001, 4844017, 4849001, 4854001, 4859017, 4864003, 4869017, 4874003,
202 4879009, 4884001, 4889033, 4894031, 4899001, 4904023, 4909007, 4914029, 4919011, 4924013,
203 4929013, 4934023, 4939003, 4944019, 4949003, 4954013, 4959013, 4964009, 4969031, 4974007,
204 4979021, 4984013, 4989029, 4994051, 4999021, 5004007, 5009003, 5014003, 5019017, 5024009,
205 5029007, 5034061, 5039017, 5044003, 5049007, 5054017, 5059001, 5064019, 5069003, 5074001,
206 5079037, 5084017, 5089013, 5094007, 5099009, 10000019, 10010023, 10020013, 10030003, 10040011,
207 10050013, 10060009, 10070029, 10080011, 10090009, 10100009, 10110007, 10120021, 10130009, 10140001,
208 10150013, 10160009, 10170023, 10180021, 10190003, 10200007, 10210007, 10220003, 10230023, 10240033,
209 10250017, 10260011, 10270009, 10280027, 10290019, 10300013, 10310021, 10320029, 10330007, 10340003,
210 10350019, 10360019, 10370011, 10380001, 10390013, 10400021, 10410011, 10420001, 10430011, 10440011,
211 10450009, 10460003, 10470017, 10480009, 10490009, 10500013, 10510009, 10520017, 10530019, 10540001,
212 10550003, 10560019, 10570009, 10580047, 10590023, 10600021, 10610003, 10620007, 10630001, 10640009,
213 10650011, 10660031, 10670003, 10680011, 10690007, 10700023, 10710001, 10720007, 10730021, 10740019,
214 10750009, 10760017, 10770013, 10780027, 10790009, 10800007, 10810001, 10820009, 10830007, 10840009,
215 10850003, 10860041, 10870003, 10880029, 10890023, 10900007, 10910017, 10920017, 10930009, 10940009,
216 10950007, 10960007, 10970023, 10980029, 10990013, 11000027, 11010007, 11020001, 11030011, 11040011,
217 11050007, 11060029, 11070001, 11080007, 11090029, 11100013, 11110031, 11120009, 11130001, 11140001,
218 11150021, 11160013, 11170001, 11180011, 11190013, 11200001, 11210009, 11220007, 11230031, 11240017,
219 11250007, 11260003, 11270027, 11280007, 11290003, 11300017, 11310011, 11320003, 11330003, 11340023,
220 11350013, 11360021, 11370013, 11380003, 11390039, 11400017, 11410037, 11420009, 11430007, 11440003,
221 11450003, 11460013, 11470003, 11480069, 11490007, 11500001, 11510027, 11520013, 11530019, 11540033,
222 11550029, 11560019, 11570003, 11580011, 11590013, 11600011, 11610013, 11620003, 11630011, 11640007,
223 11650003, 11660003, 11670011, 11680027, 11690011, 11700001, 11710007, 11720029, 11730001, 11740019,
224 11750021, 11760013, 11770013, 11780011, 11790017, 11800001, 11810003, 11820019, 11830043, 11840011,
225 11850001, 11860021, 11870009, 11880023, 11890001, 11900003, 11910043, 11920001, 11930041, 11940017,
226 11950007, 11960059, 11970017, 11980021, 11990009, 12000017, 12010013, 12020051, 12030017, 12040001,
227 12050011, 12060001, 12070021, 12080017, 12090011, 12100003, 12110003, 12120001, 12130003,
228 12140039, 12150001, 12160003, 12170009, 12180011, 12190007, 12200009, 12210007, 12220003, 12230003,
229 12240013, 12250009, 12260033, 12270047, 12280003, 12290009, 12300017, 12310013, 12320017, 12330011,
230 12340007, 12350017, 12360001, 12370003, 12380009, 12390011, 12400001, 12410009, 12420011, 12430001,
231 12440009, 12450023, 12460001, 12470009, 12480029, 12490001, 12500003, 12510023, 12520003, 12530017,
232 12540041, 12550001, 12560003, 12570031, 12580003, 12590003, 12600001, 12610027, 12620011, 12630011,
233 12640003, 12650021, 12660013, 12670003, 12680039, 12690011, 12700001, 12710003, 12720011, 12730007,
234 12740003, 12750011, 12760021, 12770053, 12780007, 12790007, 12800009, 12810013, 12820009, 12830011,
235 12840001, 12850039, 12860033, 12870001, 12880001, 12890027, 12900001, 12910013, 12920003, 12930011,
236 12940001, 12950017, 12960019, 12970007, 12980029, 12990007, 13000027, 13010047, 13020017, 13030037,
237 13040029, 13050043, 13060009, 13070009, 13080007, 13090001, 13100023, 13110047, 13120057, 13130003,
238 13140007, 13150003, 13160029, 13170029, 13180001, 13190003, 13200001, 13210013, 13220003, 13230001,
239 13240021, 13250009, 13260007, 13270003, 13280017, 13290001, 13300039, 13310009, 13320001, 13330007,
240 13340003, 13350019, 13360007, 13370003, 13380023, 13390001, 13400027, 13410031, 13420003, 13430003,
241 13440001, 13450039, 13460003, 13470011, 13480003, 13490023, 13500007, 13510001, 13520011, 13530017,
242 13540001, 13550039, 13560013, 13570001, 13580011, 13590019, 13600003, 13610021, 13620007, 13630009,
243 13640009, 13650001, 13660001, 13670009, 13680001, 13690031, 13700009, 13710013, 13720001, 13730023,
244 13740017, 13750043, 13760029, 13770011, 13780003, 13790027, 13800013, 13810031, 13820041, 13830001,
245 13840003, 13850009, 13860001, 13870039, 13880023, 13890011, 13900013, 13910003, 13920019, 13930003,
246 13940011, 13950043, 13960007, 13970009, 13980047, 13990001, 14000029, 14010019, 14020001, 14030021,
247 14040001, 14050013, 14060021, 14070019, 14080013, 14090003, 14100041, 14110007, 14120003, 14130007,
248 14140001, 14150009, 14160001, 14170003, 14180003, 14190013, 14200001, 14210039, 14220023, 14230001,
249 14240011, 14250007, 14260003, 14270017, 14280029, 14290037, 14300017, 14310001, 14320049, 14330003,
250 14340019, 14350001, 14360041, 14370047, 14380007, 14390009, 14400011, 14410003, 14420009, 14430001,
251 14440001, 14450011, 14460001, 14470003, 14480009, 14490017, 14500001, 14510003, 14520019, 14530007,
252 14540003, 14550001, 14560003, 14570027, 14580017, 14590001, 14600017, 14610007, 14620009, 14630009,
253 14640023, 14650003, 14660003, 14670011, 14680037, 14690017, 14700011, 14710019, 14720021, 14730011,
254 14740007, 14750039, 14760001, 14770003, 14780011, 14790001, 14800001, 14810023, 14820031, 14830003,
255 14840011, 14850041, 14860003, 14870017, 14880013, 14890019, 14900003, 14910017, 14920013, 14930011,
256 14940007, 14950003, 14960063, 14970001, 14980019, 14990011, 15000017, 15010001, 15020009, 15030019,
257 15040007, 15050017, 15100027, 15150001, 15200011, 15250009, 15300001, 15350003, 15400031,
258 15450013, 15500011, 15550009, 15600001, 15650003, 15700019, 15750013, 15800017, 15850019, 15900013,
259 15950009, 16000057, 16050007, 16100027, 16150003, 16200013, 16250009, 16300003, 16350001, 16400017,
260 16450003, 16500007, 16550047, 16600009, 16650001, 16700003, 16750009, 16800023, 16850003, 16900021,
261 16950013, 17000023, 17050003, 17100001, 17150011, 17200003, 17250011, 17300009, 17350001, 17400001,
262 17450021, 17500013, 17550007, 17600039, 17650001, 17700019, 17750003, 17800001, 17850013, 17900021,
263 17950001, 18000041, 18050003, 18100003, 18150019, 18200033, 18250021, 18300001, 18350009, 18400003,
264 18450001, 18500017, 18550033, 18600047, 18650041, 18700001, 18750001, 18800003, 18850019, 18900053,
265 18950003, 19000013, 19050001, 19100033, 19150051, 19200007, 19250003, 19300007, 19350011, 19400023,
266 19450001, 19500017, 19550009, 19600003, 19650019, 19700027, 19750001, 19800083, 19850009, 19900009,
267 19950013, 20000003, 20050003, 20100023, 20150021, 20200013, 20250007, 20300003, 20350049, 20400013,
268 20450009, 20500019, 20550007, 20600003, 20650009, 20700011, 20750011, 20800007, 20850001, 20900051,
269 20950009, 21000037, 21050011, 21100003, 21150001, 21200021, 21250001, 21300029, 21350009, 21400003,
270 21450019, 21500021, 21550003, 21600001, 21650011, 21700001, 21750007, 21800003, 21850027, 21900013,
271 21950011, 22000001, 22050001, 22100041, 22150001, 22200001, 22250017, 22300001, 22350001, 22400009,
272 22450003, 22500011, 22550009, 22600001, 22650007, 22700017, 22750003, 22800013, 22850011, 22900013,
273 22950001, 23000009, 23050003, 23100001, 23150009, 23200027, 23250001, 23300027, 23350003, 23400023,
274 23450003, 23500003, 23550013, 23600023, 23650001, 23700029, 23750009, 23800031, 23850023, 23900027,
275 23950001, 24000001, 24050009, 24100003, 24150001, 24200017, 24250013, 24300007, 24350047, 24400001,
276 24450031, 24500017, 24550003, 24600007, 24650009, 24700007, 24750007, 24800011, 24850027, 24900023,
277 24950011, 25000009, 25050001, 25100017, 25150001, 25200011, 25250003, 25300003, 25350001, 25400003,
278 25450001, 25500001, 25550027, 25600013, 25650011, 25700033, 25750007, 25800007, 25850003, 25900013,
279 25950017, 26000003, 26050043, 26100001, 26150053, 26200001, 26250031, 27250001, 28250023, 29250007,
280 30250001, 31250017, 32250041, 33250001, 34250011, 35250001, 36250003, 37250011, 38250011, 39250037,
281 40250011, 41250031, 42250009, 43250021, 44250001, 45250027, 46250003, 47250001, 48250001, 49250011,
282 50250017, 51250007, 52250021, 53250023, 54250003, 55250003, 56250011, 57250003, 58250047, 59250007,
283 60250027, 61250003, 62250017, 63250001, 64250009, 65250001, 66250027, 67250021, 68250001, 69250007,
284 70250023, 71250007, 72250001, 73250011, 74250013, 75250031, 76250003, 77250007, 78250001, 79250021,
285 80250011, 81250019, 82250009, 83250007, 84250003, 85250021, 86250001, 87250019, 88250021, 89250037,
286 90250007, 91250011, 92250019, 93250013, 94250027, 95250019, 96250003, 97250009, 98250011, 99250007,
287 100250011, 101250001, 102250003, 103250011, 104250019, 105250021, 106250047, 107250001, 108250001, 109250003,
288 110250013, 111250033, 112250011, 113250001, 114250001, 115250027, 116250007, 117250031, 118250021, 119250007,
289 120250019, 121250011, 122250013, 123250007, 124250003, 125250061, 126250001, 127250041, 128250013, 129250021,
290 130250009, 131250011, 132250007, 133250009, 134250073, 135250043, 136250029, 137250007, 138250027, 139250003,
291 140250007, 141250019, 142250011, 143250011, 144250009, 145250011, 146250007, 147250001, 148250023, 149250001,
292 150250019, 151250009, 152250023, 153250003, 154250053, 155250059, 156250027, 157250059, 158250007, 159250009,
293 160250003, 161250029, 162250003, 163250011, 164250013, 165250003, 166250027, 167250001, 168250001, 169250027,
294 170250001, 171250033, 172250003, 173250023, 174250003, 175250017, 176250007, 177250013, 178250003, 179250007,
295 180250001, 181250033, 182250011, 183250009, 184250009, 185250001, 186250007, 187250009, 188250019, 189250057,
296 190250083, 191250001, 192250013, 193250009, 194250031, 195250019, 196250003, 197250019, 198250007, 199250011,
297 200250013, 201250001, 202250023, 203250013, 204250009, 205250029, 206250019, 207250007, 208250039, 209250001,
298 210250003, 211250021, 212250023, 213250001, 214250041, 215250001, 216250003, 217250017, 218250007, 219250013,
299 220250003, 221250031, 222250069, 223250009, 224250017, 225250001, 226250009, 227250047, 228250027, 229250009,
300 230250017, 231250009, 232250003, 233250007, 234250039, 236250017, 238250029, 240250033, 242250013, 244250003,
301 246250003, 248250001, 250250003, 252250049, 254250019, 256250011, 258250037, 260250013, 262250003, 264250031,
302 266250043, 268250011, 270250027, 272250001, 274250021, 276250001, 278250019, 280250023, 282250021, 284250037,
303 286250021, 288250003, 290250013, 292250011, 294250003, 296250001, 298250003, 300250019, 302250007, 304250017,
304 306250069, 308250023, 310250027, 312250013, 314250017, 316250009, 318250021, 320250031, 322250021, 324250033,
305 326250011, 328250017, 330250009, 332250001, 334250011, 336250003, 338250013, 340250047, 342250009, 344250001,
306 346250011, 348250039, 350250001, 352250011, 354250009, 356250017, 358250029, 360250003, 362250011, 364250039,
307 366250009, 368250007, 370250003, 372250069, 374250029, 376250023, 378250009, 380250019, 382250003, 384250001,
308 386250019, 388250011, 390250019, 392250013, 394250027, 396250021, 398250001, 400250009, 402250001, 404250043,
309 406250041, 408250013, 410250007, 412250023, 414250021, 416250007, 418250011, 420250001, 422250011, 424250003,
310 426250049, 428250019, 430250039, 432250067, 434250007, 436250033, 438250003, 440250001, 442250027, 444250013,
311 446250037, 448250041, 450250019, 452250017, 454250009, 456250013, 458250017, 460250003, 462250007, 464250029,
312 466250069, 468250021, 470250007, 472250003, 474250019, 476250007, 478250009, 480250003, 482250037, 484250003,
313 486250003, 488250019, 490250011, 492250001, 494250007, 496250033, 498250007, 500250013, 502250059, 504250001,
314 506250007, 508250009, 510250003, 512250017, 514250039, 516250001, 518250011, 520250021, 522250033, 524250007,
315 526250003, 528250003, 530250029, 532250003, 534250019, 536250019, 538250021, 540250001, 542250013, 544250017,
316 546250007, 548250023, 550250003, 552250043, 554250019, 556250017, 558250057, 560250001, 562250021, 564250021,
317 566250001, 568250009, 570250001, 572250001, 574250003, 576250013, 578250007, 580250051, 582250001, 584250011,
318 586250011, 588250043, 590250043, 592250003, 594250009, 596250007, 598250011, 600250003, 602250023, 604250011,
319 606250003, 608250001, 610250009, 612250003, 614250011, 616250039, 618250013, 622250009, 626250007, 630250001,
320 634250009, 638250049, 642250001, 646250009, 650250001, 654250001, 658250023, 662250007, 666250021, 670250003,
321 674250067, 678250099, 682250011, 686250001, 690250049, 694250003, 698250017, 702250001, 706250033, 710250019,
322 714250001, 718250009, 722250031, 726250069, 730250029, 734250019, 738250003, 742250017, 746250041, 750250013,
323 754250039, 758250041, 762250001, 766250011, 770250011, 774250013, 778250029, 782250047, 786250021, 790250003,
324 794250011, 798250007, 802250017, 806250013, 810250019, 814250069, 818250007, 822250081, 826250053, 830250023,
325 834250049, 838250009, 842250001, 846250001, 850250021, 854250011, 858250013, 862250017, 866250013, 870250001,
326 874250017, 878250013, 882250007, 886250009, 890250017, 894250001, 898250009, 902250029, 906250013, 910250009,
327 914250019, 918250007, 922250003, 926250011, 930250001, 934250029, 938250013, 942250009, 946250009, 950250001,
328 954250009, 958250011, 962250019, 966250003, 970250023, 974250007, 978250051, 982250041, 986250017, 990250007,
329 994250017, 998250007, 1002250027, 1006250017, 1010250029, 1014250019, 1018250011, 1022250011, 1026250003, 1030250003,
330 1034250001, 1038250001, 1042250009, 1046250083, 1050250001, 1054250003, 1058250029, 1062250031, 1066250021, 1070250001,
331 1074250007, 1078250009, 1082250007, 1086250027, 1090250009, 1094250013, 1098250001, 1102250047, 1106250007, 1110250013,
332 1114250029, 1118250013, 1122250009, 1126250009, 1130250019, 1134250027, 1138250021, 1142250001, 1146250009, 1150250011,
333 1154250049, 1158250019, 1162250003, 1166250013, 1170250019, 1174250003, 1178250013, 1182250001, 1186250011, 1190250001,
334 1194250003, 1198250041, 1202250109, 1206250009, 1210250023, 1214250047, 1218250027, 1222250011, 1226250019, 1230250009,
335 1234250009, 1238250031, 1242250007, 1246250011, 1250250037, 1254250051, 1258250003, 1262250023, 1266250009, 1270250039,
336 1274250007, 1278250003, 1282250029, 1286250019, 1290250007, 1294250003, 1298250013, 1302250003, 1306250027, 1310250023,
337 1314250009, 1318250053, 1322250029, 1326250007, 1330250003, 1334250017, 1338250051, 1342250033, 1346250011, 1350250001,
338 1354250017, 1358250001, 1362250027, 1366250009, 1370250067, 1374250001, 1378250009, 1382250043, 1386250003, 1390250009,
339 1394250007, 1398250013, 1402250009, 1406250037, 1410250031, 1414250017, 1418250013, 1422250007, 1426250017, 1430250037,
340 1434250001, 1438250059, 1442250053, 1446250009, 1450250003, 1454250013, 1458250009, 1462250003, 1466250001, 1470250013,
341 1474250009, 1478250013, 1482250013, 1486250023, 1490250007, 1494250019, 1498250011, 1502250007, 1506250007, 1510250057,
342 1514250013, 1518250051, 1522250029, 1526250013, 1530250003, 1534250009, 1538250017, 1542250009, 1546250047, 1550250001,
343 1554250021, 1558250009, 1562250007, 1566250019, 1570250029, 1574250053, 1578250007, 1582250009, 1586250007, 1590250009,
344 1594250029, 1598250007, 1602250003, 1609250047, 1616250023, 1623250021, 1630250023, 1637250011, 1644250009, 1651250011,
345 1658250029, 1665250001, 1672250009, 1679250031, 1686250021, 1693250003, 1700250001, 1707250001, 1714250009, 1721250001,
346 1728250003, 1735250021, 1742250001, 1749250049, 1756250011, 1763250001, 1770250003, 1777250011, 1784250023, 1791250003,
347 1798250011, 1805250019, 1812250073, 1819250047, 1826250011, 1833250009, 1840250003, 1847250001, 1854250003, 1861250021,
348 1868250011, 1875250001, 1882250023, 1889250059, 1896250007, 1903250017, 1910250007, 1917250003, 1924250033, 1931250023,
349 1938250007, 1945250009, 1952250031, 1959250001, 1966250003, 1973250007, 1980250001, 1987250017, 1994250017, 2001250019,
350 2008250003, 2015250001, 2022250003, 2029250053, 2036250019, 2043250003, 2050250003, 2057250001, 2064250033, 2071250009,
351 2078250007, 2085250001, 2092250051, 2099250029, 2106250031, 2113250011, 2120250029, 2127250009, 2134250009, 2141250029,
352 2148250001, 2155250039, 2162250007, 2169250009, 2176250009, 2183250001, 2190250019, 2197250087, 2204250023, 2211250009,
353 2218250009, 2225250059, 2232250001, 2239250009, 2246250023, 2253250007, 2260250023, 2267250017, 2274250001, 2281250003,
354 2288250023, 2295250007, 2302250009, 2309250001, 2316250019, 2323250009, 2330250089, 2337250009, 2344250021, 2351250007,
355 2358250003, 2365250003, 2372250017, 2379250007, 2386250047, 2393250007, 2400250037, 2407250063, 2414250001, 2421250019,
356 2428250003, 2435250001, 2442250001, 2449250021, 2456250019, 2463250001, 2470250011, 2477250007, 2484250061, 2491250011,
357 2498250047, 2505250001, 2512250009, 2519250023, 2526250003, 2533250003, 2540250067, 2547250033, 2554250003, 2561250023,
358 2568250001, 2575250009, 2582250001, 2589250049, 2596250009, 2603250019, 2610250021, 2617250003, 2624250017, 2631250007,
359 2638250011, 2645250011, 2652250031, 2659250023, 2666250001, 2673250043, 2680250011, 2687250037, 2694250003, 2701250021,
360 2708250011, 2715250001, 2722250009, 2729250031, 2736250001, 2743250011, 2750250011, 2757250033, 2764250003, 2771250029,
361 2778250001, 2785250053, 2792250059, 2799250001, 2806250053, 2813250007, 2820250007, 2827250029, 2834250017, 2841250003,
362 2848250021, 2855250001, 2862250007, 2869250017, 2876250007, 2883250001, 2890250003, 2897250011, 2904250001, 2911250009,
363 2918250043, 2925250019, 2932250003, 2939250007, 2946250001, 2953250011, 2960250017, 2967250021, 2974250039, 2981250029,
364 2988250003, 2995250033, 3002250001, 3009250009, 3016250021, 3023250001, 3030250001, 3037250009, 3044250007, 3051250003,
365 3063250013, 3072250033, 3081250013, 3090250001, 3099250001, 3108250007, 3117250039, 3126250007, 3135250003, 3144250003,
366 3153250007, 3162250027, 3171250037, 3180250009, 3189250021, 3198250037, 3207250069, 3216250021, 3225250009, 3234250001,
367 3243250051, 3252250031, 3261250021, 3270250019, 3279250021, 3288250001, 3297250001, 3306250001, 3315250009, 3324250003,
368 3333250003, 3342250003, 3351250003, 3360250013, 3369250019, 3378250019, 3387250007, 3396250009, 3405250007, 3414250013,
369 3423250021, 3432250007, 3441250027, 3450250009, 3459250009, 3468250001, 3477250001, 3486250021, 3495250019, 3504250021,
370 3513250009, 3522250031, 3531250003, 3540250009, 3549250007, 3558250001, 3567250003, 3576250001, 3585250007, 3594250021,
371 3603250073, 3612250003, 3621250037, 3630250027, 3639250001, 3648250007, 3657250021, 3666250109, 3675250001, 3684250007,
372 3693250009, 3702250009, 3711250001, 3720250003, 3729250001, 3738250013, 3747250019, 3756250021, 3765250031, 3774250027,
373 3783250019, 3792250019, 3801250001, 3810250019, 3819250007, 3828250003, 3837250019, 3846250021, 3855250013, 3864250081,
374 3873250001, 3882250003, 3891250001, 3900250033, 3909250043, 3918250033, 3927250001, 3936250013, 3945250019, 3954250039,
375 3963250003, 3972250003
376 };
377
378 // num of entries of array above
379 const size_t numPrimes = sizeof(primeList) / sizeof(primeList[0]);
380
381 const unsigned long DefaultPrime = primeList[0];
382
383 size_t next_prime(unsigned long n)
384 {
385 // Return the smallest prime number p such that p >= n.
386 //
387 // For small n (below the first entry in primeList) we fall back to a
388 // direct primality test.
389
390 if (n <= 2)
391 return 2;
392
393 if (n < primeList[0])
394 {
395 unsigned long p = n;
396 if (p % 2 == 0)
397 ++p;
398 while (not Primes::is_prime(p))
399 p += 2;
400 return p;
401 }
402
403 // For n >= primeList[0], we use the precomputed list.
404 auto it = std::lower_bound(std::begin(primeList), std::end(primeList), n);
405 if (it != std::end(primeList))
406 return *it;
407
408 return Primes::next_prime_number_greater_than(n);
409 }
410
411 bool check_primes_database()
412 {
413 for (size_t i = 1; i < numPrimes; ++i)
414 if (primeList[i] <= primeList[i - 1])
415 return false;
416 return true;
417 }
418
419
420}
ah-errors.H
Exception handling system with formatted messages for Aleph-w.
Primes::next_prime_number_greater_than
unsigned long next_prime_number_greater_than(unsigned long n)
Find the next prime strictly greater than n.
Definition primes.H:161
Primes::primeList
const unsigned long primeList[]
Pre-computed array of prime numbers for fast lookup.
Definition primes.C:45
Primes::numPrimes
const size_t numPrimes
Number of primes in the pre-computed database.
Definition primes.C:379
Primes::DefaultPrime
const unsigned long DefaultPrime
Default prime number used when no specific size is requested.
Definition primes.C:381
Primes::check_primes_database
bool check_primes_database()
Verify the integrity of the prime database.
Definition primes.C:411
Primes::is_prime
bool is_prime(unsigned long n)
Test if a number is prime using trial division.
Definition primes.H:128
Primes::next_prime
size_t next_prime(unsigned long n)
Find the smallest prime number >= n from the database.
Definition primes.C:383
primes.H
Prime number utilities for hash tables and mathematical operations.