2 ** Copyright (C) 2002 by Kevin L. Mitchell <klmitch@mit.edu>
4 ** This library is free software; you can redistribute it and/or
5 ** modify it under the terms of the GNU Library General Public
6 ** License as published by the Free Software Foundation; either
7 ** version 2 of the License, or (at your option) any later version.
9 ** This library is distributed in the hope that it will be useful,
10 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
11 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 ** Library General Public License for more details.
14 ** You should have received a copy of the GNU Library General Public
15 ** License along with this library; if not, write to the Free
16 ** Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
22 #include "dbprim_int.h"
26 #define MAX_PRIME 4294967291UL
28 /* Table of all 16-bit primes plus two extra--used for checking computed
29 * primes for primality.
31 static unsigned long primes[] = {
32 3, 5, 7, 11, 13, 17, 19, 23, 29,
33 31, 37, 41, 43, 47, 53, 59, 61, 67,
34 71, 73, 79, 83, 89, 97, 101, 103, 107,
35 109, 113, 127, 131, 137, 139, 149, 151, 157,
36 163, 167, 173, 179, 181, 191, 193, 197, 199,
37 211, 223, 227, 229, 233, 239, 241, 251, 257,
38 263, 269, 271, 277, 281, 283, 293, 307, 311,
39 313, 317, 331, 337, 347, 349, 353, 359, 367,
40 373, 379, 383, 389, 397, 401, 409, 419, 421,
41 431, 433, 439, 443, 449, 457, 461, 463, 467,
42 479, 487, 491, 499, 503, 509, 521, 523, 541,
43 547, 557, 563, 569, 571, 577, 587, 593, 599,
44 601, 607, 613, 617, 619, 631, 641, 643, 647,
45 653, 659, 661, 673, 677, 683, 691, 701, 709,
46 719, 727, 733, 739, 743, 751, 757, 761, 769,
47 773, 787, 797, 809, 811, 821, 823, 827, 829,
48 839, 853, 857, 859, 863, 877, 881, 883, 887,
49 907, 911, 919, 929, 937, 941, 947, 953, 967,
50 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021,
51 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087,
52 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
53 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217,
54 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,
55 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327,
56 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429,
57 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483,
58 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549,
59 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607,
60 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
61 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741,
62 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
63 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879,
64 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973,
65 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027,
66 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089,
67 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153,
68 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
69 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309,
70 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377,
71 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437,
72 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,
73 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609,
74 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677,
75 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719,
76 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
77 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857,
78 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939,
79 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019,
80 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089,
81 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187,
82 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257,
83 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329,
84 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
85 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469,
86 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541,
87 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613,
88 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677,
89 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761,
90 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833,
91 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911,
92 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
93 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051,
94 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129,
95 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217,
96 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271,
97 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357,
98 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447,
99 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517,
100 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
101 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663,
102 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751,
103 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817,
104 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931,
105 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987,
106 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051,
107 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119,
108 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227,
109 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303,
110 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399,
111 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449,
112 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521,
113 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623,
114 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683,
115 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749,
116 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839,
117 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881,
118 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007,
119 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079,
120 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151,
121 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229,
122 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301,
123 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361,
124 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451,
125 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553,
126 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637,
127 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703,
128 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791,
129 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863,
130 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949,
131 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001,
132 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103,
133 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193,
134 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253,
135 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351,
136 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477,
137 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537,
138 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589,
139 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673,
140 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741,
141 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841,
142 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919,
143 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011,
144 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093,
145 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179,
146 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263,
147 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329,
148 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429,
149 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527,
150 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609,
151 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681,
152 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741,
153 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821,
154 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893,
155 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999,
156 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059,
157 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157,
158 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227,
159 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319,
160 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397,
161 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461,
162 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533,
163 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629,
164 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719,
165 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787,
166 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857,
167 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931,
168 9941, 9949, 9967, 9973, 10007, 10009, 10037, 10039, 10061,
169 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133,
170 10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193,
171 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271, 10273,
172 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343,
173 10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457,
174 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531,
175 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631,
176 10639, 10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711,
177 10723, 10729, 10733, 10739, 10753, 10771, 10781, 10789, 10799,
178 10831, 10837, 10847, 10853, 10859, 10861, 10867, 10883, 10889,
179 10891, 10903, 10909, 10937, 10939, 10949, 10957, 10973, 10979,
180 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071,
181 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159,
182 11161, 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251,
183 11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317, 11321,
184 11329, 11351, 11353, 11369, 11383, 11393, 11399, 11411, 11423,
185 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491, 11497,
186 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597,
187 11617, 11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701,
188 11717, 11719, 11731, 11743, 11777, 11779, 11783, 11789, 11801,
189 11807, 11813, 11821, 11827, 11831, 11833, 11839, 11863, 11867,
190 11887, 11897, 11903, 11909, 11923, 11927, 11933, 11939, 11941,
191 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037,
192 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109,
193 12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197, 12203,
194 12211, 12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277,
195 12281, 12289, 12301, 12323, 12329, 12343, 12347, 12373, 12377,
196 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437, 12451,
197 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517,
198 12527, 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589,
199 12601, 12611, 12613, 12619, 12637, 12641, 12647, 12653, 12659,
200 12671, 12689, 12697, 12703, 12713, 12721, 12739, 12743, 12757,
201 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829, 12841,
202 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923,
203 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003,
204 13007, 13009, 13033, 13037, 13043, 13049, 13063, 13093, 13099,
205 13103, 13109, 13121, 13127, 13147, 13151, 13159, 13163, 13171,
206 13177, 13183, 13187, 13217, 13219, 13229, 13241, 13249, 13259,
207 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337, 13339,
208 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451,
209 13457, 13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537,
210 13553, 13567, 13577, 13591, 13597, 13613, 13619, 13627, 13633,
211 13649, 13669, 13679, 13681, 13687, 13691, 13693, 13697, 13709,
212 13711, 13721, 13723, 13729, 13751, 13757, 13759, 13763, 13781,
213 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877,
214 13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933,
215 13963, 13967, 13997, 13999, 14009, 14011, 14029, 14033, 14051,
216 14057, 14071, 14081, 14083, 14087, 14107, 14143, 14149, 14153,
217 14159, 14173, 14177, 14197, 14207, 14221, 14243, 14249, 14251,
218 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347, 14369,
219 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437,
220 14447, 14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537,
221 14543, 14549, 14551, 14557, 14561, 14563, 14591, 14593, 14621,
222 14627, 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699,
223 14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753, 14759,
224 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831,
225 14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923,
226 14929, 14939, 14947, 14951, 14957, 14969, 14983, 15013, 15017,
227 15031, 15053, 15061, 15073, 15077, 15083, 15091, 15101, 15107,
228 15121, 15131, 15137, 15139, 15149, 15161, 15173, 15187, 15193,
229 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269, 15271,
230 15277, 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331,
231 15349, 15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413,
232 15427, 15439, 15443, 15451, 15461, 15467, 15473, 15493, 15497,
233 15511, 15527, 15541, 15551, 15559, 15569, 15581, 15583, 15601,
234 15607, 15619, 15629, 15641, 15643, 15647, 15649, 15661, 15667,
235 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749,
236 15761, 15767, 15773, 15787, 15791, 15797, 15803, 15809, 15817,
237 15823, 15859, 15877, 15881, 15887, 15889, 15901, 15907, 15913,
238 15919, 15923, 15937, 15959, 15971, 15973, 15991, 16001, 16007,
239 16033, 16057, 16061, 16063, 16067, 16069, 16073, 16087, 16091,
240 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187, 16189,
241 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267, 16273,
242 16301, 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381,
243 16411, 16417, 16421, 16427, 16433, 16447, 16451, 16453, 16477,
244 16481, 16487, 16493, 16519, 16529, 16547, 16553, 16561, 16567,
245 16573, 16603, 16607, 16619, 16631, 16633, 16649, 16651, 16657,
246 16661, 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747,
247 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871,
248 16879, 16883, 16889, 16901, 16903, 16921, 16927, 16931, 16937,
249 16943, 16963, 16979, 16981, 16987, 16993, 17011, 17021, 17027,
250 17029, 17033, 17041, 17047, 17053, 17077, 17093, 17099, 17107,
251 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191, 17203,
252 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317,
253 17321, 17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387,
254 17389, 17393, 17401, 17417, 17419, 17431, 17443, 17449, 17467,
255 17471, 17477, 17483, 17489, 17491, 17497, 17509, 17519, 17539,
256 17551, 17569, 17573, 17579, 17581, 17597, 17599, 17609, 17623,
257 17627, 17657, 17659, 17669, 17681, 17683, 17707, 17713, 17729,
258 17737, 17747, 17749, 17761, 17783, 17789, 17791, 17807, 17827,
259 17837, 17839, 17851, 17863, 17881, 17891, 17903, 17909, 17911,
260 17921, 17923, 17929, 17939, 17957, 17959, 17971, 17977, 17981,
261 17987, 17989, 18013, 18041, 18043, 18047, 18049, 18059, 18061,
262 18077, 18089, 18097, 18119, 18121, 18127, 18131, 18133, 18143,
263 18149, 18169, 18181, 18191, 18199, 18211, 18217, 18223, 18229,
264 18233, 18251, 18253, 18257, 18269, 18287, 18289, 18301, 18307,
265 18311, 18313, 18329, 18341, 18353, 18367, 18371, 18379, 18397,
266 18401, 18413, 18427, 18433, 18439, 18443, 18451, 18457, 18461,
267 18481, 18493, 18503, 18517, 18521, 18523, 18539, 18541, 18553,
268 18583, 18587, 18593, 18617, 18637, 18661, 18671, 18679, 18691,
269 18701, 18713, 18719, 18731, 18743, 18749, 18757, 18773, 18787,
270 18793, 18797, 18803, 18839, 18859, 18869, 18899, 18911, 18913,
271 18917, 18919, 18947, 18959, 18973, 18979, 19001, 19009, 19013,
272 19031, 19037, 19051, 19069, 19073, 19079, 19081, 19087, 19121,
273 19139, 19141, 19157, 19163, 19181, 19183, 19207, 19211, 19213,
274 19219, 19231, 19237, 19249, 19259, 19267, 19273, 19289, 19301,
275 19309, 19319, 19333, 19373, 19379, 19381, 19387, 19391, 19403,
276 19417, 19421, 19423, 19427, 19429, 19433, 19441, 19447, 19457,
277 19463, 19469, 19471, 19477, 19483, 19489, 19501, 19507, 19531,
278 19541, 19543, 19553, 19559, 19571, 19577, 19583, 19597, 19603,
279 19609, 19661, 19681, 19687, 19697, 19699, 19709, 19717, 19727,
280 19739, 19751, 19753, 19759, 19763, 19777, 19793, 19801, 19813,
281 19819, 19841, 19843, 19853, 19861, 19867, 19889, 19891, 19913,
282 19919, 19927, 19937, 19949, 19961, 19963, 19973, 19979, 19991,
283 19993, 19997, 20011, 20021, 20023, 20029, 20047, 20051, 20063,
284 20071, 20089, 20101, 20107, 20113, 20117, 20123, 20129, 20143,
285 20147, 20149, 20161, 20173, 20177, 20183, 20201, 20219, 20231,
286 20233, 20249, 20261, 20269, 20287, 20297, 20323, 20327, 20333,
287 20341, 20347, 20353, 20357, 20359, 20369, 20389, 20393, 20399,
288 20407, 20411, 20431, 20441, 20443, 20477, 20479, 20483, 20507,
289 20509, 20521, 20533, 20543, 20549, 20551, 20563, 20593, 20599,
290 20611, 20627, 20639, 20641, 20663, 20681, 20693, 20707, 20717,
291 20719, 20731, 20743, 20747, 20749, 20753, 20759, 20771, 20773,
292 20789, 20807, 20809, 20849, 20857, 20873, 20879, 20887, 20897,
293 20899, 20903, 20921, 20929, 20939, 20947, 20959, 20963, 20981,
294 20983, 21001, 21011, 21013, 21017, 21019, 21023, 21031, 21059,
295 21061, 21067, 21089, 21101, 21107, 21121, 21139, 21143, 21149,
296 21157, 21163, 21169, 21179, 21187, 21191, 21193, 21211, 21221,
297 21227, 21247, 21269, 21277, 21283, 21313, 21317, 21319, 21323,
298 21341, 21347, 21377, 21379, 21383, 21391, 21397, 21401, 21407,
299 21419, 21433, 21467, 21481, 21487, 21491, 21493, 21499, 21503,
300 21517, 21521, 21523, 21529, 21557, 21559, 21563, 21569, 21577,
301 21587, 21589, 21599, 21601, 21611, 21613, 21617, 21647, 21649,
302 21661, 21673, 21683, 21701, 21713, 21727, 21737, 21739, 21751,
303 21757, 21767, 21773, 21787, 21799, 21803, 21817, 21821, 21839,
304 21841, 21851, 21859, 21863, 21871, 21881, 21893, 21911, 21929,
305 21937, 21943, 21961, 21977, 21991, 21997, 22003, 22013, 22027,
306 22031, 22037, 22039, 22051, 22063, 22067, 22073, 22079, 22091,
307 22093, 22109, 22111, 22123, 22129, 22133, 22147, 22153, 22157,
308 22159, 22171, 22189, 22193, 22229, 22247, 22259, 22271, 22273,
309 22277, 22279, 22283, 22291, 22303, 22307, 22343, 22349, 22367,
310 22369, 22381, 22391, 22397, 22409, 22433, 22441, 22447, 22453,
311 22469, 22481, 22483, 22501, 22511, 22531, 22541, 22543, 22549,
312 22567, 22571, 22573, 22613, 22619, 22621, 22637, 22639, 22643,
313 22651, 22669, 22679, 22691, 22697, 22699, 22709, 22717, 22721,
314 22727, 22739, 22741, 22751, 22769, 22777, 22783, 22787, 22807,
315 22811, 22817, 22853, 22859, 22861, 22871, 22877, 22901, 22907,
316 22921, 22937, 22943, 22961, 22963, 22973, 22993, 23003, 23011,
317 23017, 23021, 23027, 23029, 23039, 23041, 23053, 23057, 23059,
318 23063, 23071, 23081, 23087, 23099, 23117, 23131, 23143, 23159,
319 23167, 23173, 23189, 23197, 23201, 23203, 23209, 23227, 23251,
320 23269, 23279, 23291, 23293, 23297, 23311, 23321, 23327, 23333,
321 23339, 23357, 23369, 23371, 23399, 23417, 23431, 23447, 23459,
322 23473, 23497, 23509, 23531, 23537, 23539, 23549, 23557, 23561,
323 23563, 23567, 23581, 23593, 23599, 23603, 23609, 23623, 23627,
324 23629, 23633, 23663, 23669, 23671, 23677, 23687, 23689, 23719,
325 23741, 23743, 23747, 23753, 23761, 23767, 23773, 23789, 23801,
326 23813, 23819, 23827, 23831, 23833, 23857, 23869, 23873, 23879,
327 23887, 23893, 23899, 23909, 23911, 23917, 23929, 23957, 23971,
328 23977, 23981, 23993, 24001, 24007, 24019, 24023, 24029, 24043,
329 24049, 24061, 24071, 24077, 24083, 24091, 24097, 24103, 24107,
330 24109, 24113, 24121, 24133, 24137, 24151, 24169, 24179, 24181,
331 24197, 24203, 24223, 24229, 24239, 24247, 24251, 24281, 24317,
332 24329, 24337, 24359, 24371, 24373, 24379, 24391, 24407, 24413,
333 24419, 24421, 24439, 24443, 24469, 24473, 24481, 24499, 24509,
334 24517, 24527, 24533, 24547, 24551, 24571, 24593, 24611, 24623,
335 24631, 24659, 24671, 24677, 24683, 24691, 24697, 24709, 24733,
336 24749, 24763, 24767, 24781, 24793, 24799, 24809, 24821, 24841,
337 24847, 24851, 24859, 24877, 24889, 24907, 24917, 24919, 24923,
338 24943, 24953, 24967, 24971, 24977, 24979, 24989, 25013, 25031,
339 25033, 25037, 25057, 25073, 25087, 25097, 25111, 25117, 25121,
340 25127, 25147, 25153, 25163, 25169, 25171, 25183, 25189, 25219,
341 25229, 25237, 25243, 25247, 25253, 25261, 25301, 25303, 25307,
342 25309, 25321, 25339, 25343, 25349, 25357, 25367, 25373, 25391,
343 25409, 25411, 25423, 25439, 25447, 25453, 25457, 25463, 25469,
344 25471, 25523, 25537, 25541, 25561, 25577, 25579, 25583, 25589,
345 25601, 25603, 25609, 25621, 25633, 25639, 25643, 25657, 25667,
346 25673, 25679, 25693, 25703, 25717, 25733, 25741, 25747, 25759,
347 25763, 25771, 25793, 25799, 25801, 25819, 25841, 25847, 25849,
348 25867, 25873, 25889, 25903, 25913, 25919, 25931, 25933, 25939,
349 25943, 25951, 25969, 25981, 25997, 25999, 26003, 26017, 26021,
350 26029, 26041, 26053, 26083, 26099, 26107, 26111, 26113, 26119,
351 26141, 26153, 26161, 26171, 26177, 26183, 26189, 26203, 26209,
352 26227, 26237, 26249, 26251, 26261, 26263, 26267, 26293, 26297,
353 26309, 26317, 26321, 26339, 26347, 26357, 26371, 26387, 26393,
354 26399, 26407, 26417, 26423, 26431, 26437, 26449, 26459, 26479,
355 26489, 26497, 26501, 26513, 26539, 26557, 26561, 26573, 26591,
356 26597, 26627, 26633, 26641, 26647, 26669, 26681, 26683, 26687,
357 26693, 26699, 26701, 26711, 26713, 26717, 26723, 26729, 26731,
358 26737, 26759, 26777, 26783, 26801, 26813, 26821, 26833, 26839,
359 26849, 26861, 26863, 26879, 26881, 26891, 26893, 26903, 26921,
360 26927, 26947, 26951, 26953, 26959, 26981, 26987, 26993, 27011,
361 27017, 27031, 27043, 27059, 27061, 27067, 27073, 27077, 27091,
362 27103, 27107, 27109, 27127, 27143, 27179, 27191, 27197, 27211,
363 27239, 27241, 27253, 27259, 27271, 27277, 27281, 27283, 27299,
364 27329, 27337, 27361, 27367, 27397, 27407, 27409, 27427, 27431,
365 27437, 27449, 27457, 27479, 27481, 27487, 27509, 27527, 27529,
366 27539, 27541, 27551, 27581, 27583, 27611, 27617, 27631, 27647,
367 27653, 27673, 27689, 27691, 27697, 27701, 27733, 27737, 27739,
368 27743, 27749, 27751, 27763, 27767, 27773, 27779, 27791, 27793,
369 27799, 27803, 27809, 27817, 27823, 27827, 27847, 27851, 27883,
370 27893, 27901, 27917, 27919, 27941, 27943, 27947, 27953, 27961,
371 27967, 27983, 27997, 28001, 28019, 28027, 28031, 28051, 28057,
372 28069, 28081, 28087, 28097, 28099, 28109, 28111, 28123, 28151,
373 28163, 28181, 28183, 28201, 28211, 28219, 28229, 28277, 28279,
374 28283, 28289, 28297, 28307, 28309, 28319, 28349, 28351, 28387,
375 28393, 28403, 28409, 28411, 28429, 28433, 28439, 28447, 28463,
376 28477, 28493, 28499, 28513, 28517, 28537, 28541, 28547, 28549,
377 28559, 28571, 28573, 28579, 28591, 28597, 28603, 28607, 28619,
378 28621, 28627, 28631, 28643, 28649, 28657, 28661, 28663, 28669,
379 28687, 28697, 28703, 28711, 28723, 28729, 28751, 28753, 28759,
380 28771, 28789, 28793, 28807, 28813, 28817, 28837, 28843, 28859,
381 28867, 28871, 28879, 28901, 28909, 28921, 28927, 28933, 28949,
382 28961, 28979, 29009, 29017, 29021, 29023, 29027, 29033, 29059,
383 29063, 29077, 29101, 29123, 29129, 29131, 29137, 29147, 29153,
384 29167, 29173, 29179, 29191, 29201, 29207, 29209, 29221, 29231,
385 29243, 29251, 29269, 29287, 29297, 29303, 29311, 29327, 29333,
386 29339, 29347, 29363, 29383, 29387, 29389, 29399, 29401, 29411,
387 29423, 29429, 29437, 29443, 29453, 29473, 29483, 29501, 29527,
388 29531, 29537, 29567, 29569, 29573, 29581, 29587, 29599, 29611,
389 29629, 29633, 29641, 29663, 29669, 29671, 29683, 29717, 29723,
390 29741, 29753, 29759, 29761, 29789, 29803, 29819, 29833, 29837,
391 29851, 29863, 29867, 29873, 29879, 29881, 29917, 29921, 29927,
392 29947, 29959, 29983, 29989, 30011, 30013, 30029, 30047, 30059,
393 30071, 30089, 30091, 30097, 30103, 30109, 30113, 30119, 30133,
394 30137, 30139, 30161, 30169, 30181, 30187, 30197, 30203, 30211,
395 30223, 30241, 30253, 30259, 30269, 30271, 30293, 30307, 30313,
396 30319, 30323, 30341, 30347, 30367, 30389, 30391, 30403, 30427,
397 30431, 30449, 30467, 30469, 30491, 30493, 30497, 30509, 30517,
398 30529, 30539, 30553, 30557, 30559, 30577, 30593, 30631, 30637,
399 30643, 30649, 30661, 30671, 30677, 30689, 30697, 30703, 30707,
400 30713, 30727, 30757, 30763, 30773, 30781, 30803, 30809, 30817,
401 30829, 30839, 30841, 30851, 30853, 30859, 30869, 30871, 30881,
402 30893, 30911, 30931, 30937, 30941, 30949, 30971, 30977, 30983,
403 31013, 31019, 31033, 31039, 31051, 31063, 31069, 31079, 31081,
404 31091, 31121, 31123, 31139, 31147, 31151, 31153, 31159, 31177,
405 31181, 31183, 31189, 31193, 31219, 31223, 31231, 31237, 31247,
406 31249, 31253, 31259, 31267, 31271, 31277, 31307, 31319, 31321,
407 31327, 31333, 31337, 31357, 31379, 31387, 31391, 31393, 31397,
408 31469, 31477, 31481, 31489, 31511, 31513, 31517, 31531, 31541,
409 31543, 31547, 31567, 31573, 31583, 31601, 31607, 31627, 31643,
410 31649, 31657, 31663, 31667, 31687, 31699, 31721, 31723, 31727,
411 31729, 31741, 31751, 31769, 31771, 31793, 31799, 31817, 31847,
412 31849, 31859, 31873, 31883, 31891, 31907, 31957, 31963, 31973,
413 31981, 31991, 32003, 32009, 32027, 32029, 32051, 32057, 32059,
414 32063, 32069, 32077, 32083, 32089, 32099, 32117, 32119, 32141,
415 32143, 32159, 32173, 32183, 32189, 32191, 32203, 32213, 32233,
416 32237, 32251, 32257, 32261, 32297, 32299, 32303, 32309, 32321,
417 32323, 32327, 32341, 32353, 32359, 32363, 32369, 32371, 32377,
418 32381, 32401, 32411, 32413, 32423, 32429, 32441, 32443, 32467,
419 32479, 32491, 32497, 32503, 32507, 32531, 32533, 32537, 32561,
420 32563, 32569, 32573, 32579, 32587, 32603, 32609, 32611, 32621,
421 32633, 32647, 32653, 32687, 32693, 32707, 32713, 32717, 32719,
422 32749, 32771, 32779, 32783, 32789, 32797, 32801, 32803, 32831,
423 32833, 32839, 32843, 32869, 32887, 32909, 32911, 32917, 32933,
424 32939, 32941, 32957, 32969, 32971, 32983, 32987, 32993, 32999,
425 33013, 33023, 33029, 33037, 33049, 33053, 33071, 33073, 33083,
426 33091, 33107, 33113, 33119, 33149, 33151, 33161, 33179, 33181,
427 33191, 33199, 33203, 33211, 33223, 33247, 33287, 33289, 33301,
428 33311, 33317, 33329, 33331, 33343, 33347, 33349, 33353, 33359,
429 33377, 33391, 33403, 33409, 33413, 33427, 33457, 33461, 33469,
430 33479, 33487, 33493, 33503, 33521, 33529, 33533, 33547, 33563,
431 33569, 33577, 33581, 33587, 33589, 33599, 33601, 33613, 33617,
432 33619, 33623, 33629, 33637, 33641, 33647, 33679, 33703, 33713,
433 33721, 33739, 33749, 33751, 33757, 33767, 33769, 33773, 33791,
434 33797, 33809, 33811, 33827, 33829, 33851, 33857, 33863, 33871,
435 33889, 33893, 33911, 33923, 33931, 33937, 33941, 33961, 33967,
436 33997, 34019, 34031, 34033, 34039, 34057, 34061, 34123, 34127,
437 34129, 34141, 34147, 34157, 34159, 34171, 34183, 34211, 34213,
438 34217, 34231, 34253, 34259, 34261, 34267, 34273, 34283, 34297,
439 34301, 34303, 34313, 34319, 34327, 34337, 34351, 34361, 34367,
440 34369, 34381, 34403, 34421, 34429, 34439, 34457, 34469, 34471,
441 34483, 34487, 34499, 34501, 34511, 34513, 34519, 34537, 34543,
442 34549, 34583, 34589, 34591, 34603, 34607, 34613, 34631, 34649,
443 34651, 34667, 34673, 34679, 34687, 34693, 34703, 34721, 34729,
444 34739, 34747, 34757, 34759, 34763, 34781, 34807, 34819, 34841,
445 34843, 34847, 34849, 34871, 34877, 34883, 34897, 34913, 34919,
446 34939, 34949, 34961, 34963, 34981, 35023, 35027, 35051, 35053,
447 35059, 35069, 35081, 35083, 35089, 35099, 35107, 35111, 35117,
448 35129, 35141, 35149, 35153, 35159, 35171, 35201, 35221, 35227,
449 35251, 35257, 35267, 35279, 35281, 35291, 35311, 35317, 35323,
450 35327, 35339, 35353, 35363, 35381, 35393, 35401, 35407, 35419,
451 35423, 35437, 35447, 35449, 35461, 35491, 35507, 35509, 35521,
452 35527, 35531, 35533, 35537, 35543, 35569, 35573, 35591, 35593,
453 35597, 35603, 35617, 35671, 35677, 35729, 35731, 35747, 35753,
454 35759, 35771, 35797, 35801, 35803, 35809, 35831, 35837, 35839,
455 35851, 35863, 35869, 35879, 35897, 35899, 35911, 35923, 35933,
456 35951, 35963, 35969, 35977, 35983, 35993, 35999, 36007, 36011,
457 36013, 36017, 36037, 36061, 36067, 36073, 36083, 36097, 36107,
458 36109, 36131, 36137, 36151, 36161, 36187, 36191, 36209, 36217,
459 36229, 36241, 36251, 36263, 36269, 36277, 36293, 36299, 36307,
460 36313, 36319, 36341, 36343, 36353, 36373, 36383, 36389, 36433,
461 36451, 36457, 36467, 36469, 36473, 36479, 36493, 36497, 36523,
462 36527, 36529, 36541, 36551, 36559, 36563, 36571, 36583, 36587,
463 36599, 36607, 36629, 36637, 36643, 36653, 36671, 36677, 36683,
464 36691, 36697, 36709, 36713, 36721, 36739, 36749, 36761, 36767,
465 36779, 36781, 36787, 36791, 36793, 36809, 36821, 36833, 36847,
466 36857, 36871, 36877, 36887, 36899, 36901, 36913, 36919, 36923,
467 36929, 36931, 36943, 36947, 36973, 36979, 36997, 37003, 37013,
468 37019, 37021, 37039, 37049, 37057, 37061, 37087, 37097, 37117,
469 37123, 37139, 37159, 37171, 37181, 37189, 37199, 37201, 37217,
470 37223, 37243, 37253, 37273, 37277, 37307, 37309, 37313, 37321,
471 37337, 37339, 37357, 37361, 37363, 37369, 37379, 37397, 37409,
472 37423, 37441, 37447, 37463, 37483, 37489, 37493, 37501, 37507,
473 37511, 37517, 37529, 37537, 37547, 37549, 37561, 37567, 37571,
474 37573, 37579, 37589, 37591, 37607, 37619, 37633, 37643, 37649,
475 37657, 37663, 37691, 37693, 37699, 37717, 37747, 37781, 37783,
476 37799, 37811, 37813, 37831, 37847, 37853, 37861, 37871, 37879,
477 37889, 37897, 37907, 37951, 37957, 37963, 37967, 37987, 37991,
478 37993, 37997, 38011, 38039, 38047, 38053, 38069, 38083, 38113,
479 38119, 38149, 38153, 38167, 38177, 38183, 38189, 38197, 38201,
480 38219, 38231, 38237, 38239, 38261, 38273, 38281, 38287, 38299,
481 38303, 38317, 38321, 38327, 38329, 38333, 38351, 38371, 38377,
482 38393, 38431, 38447, 38449, 38453, 38459, 38461, 38501, 38543,
483 38557, 38561, 38567, 38569, 38593, 38603, 38609, 38611, 38629,
484 38639, 38651, 38653, 38669, 38671, 38677, 38693, 38699, 38707,
485 38711, 38713, 38723, 38729, 38737, 38747, 38749, 38767, 38783,
486 38791, 38803, 38821, 38833, 38839, 38851, 38861, 38867, 38873,
487 38891, 38903, 38917, 38921, 38923, 38933, 38953, 38959, 38971,
488 38977, 38993, 39019, 39023, 39041, 39043, 39047, 39079, 39089,
489 39097, 39103, 39107, 39113, 39119, 39133, 39139, 39157, 39161,
490 39163, 39181, 39191, 39199, 39209, 39217, 39227, 39229, 39233,
491 39239, 39241, 39251, 39293, 39301, 39313, 39317, 39323, 39341,
492 39343, 39359, 39367, 39371, 39373, 39383, 39397, 39409, 39419,
493 39439, 39443, 39451, 39461, 39499, 39503, 39509, 39511, 39521,
494 39541, 39551, 39563, 39569, 39581, 39607, 39619, 39623, 39631,
495 39659, 39667, 39671, 39679, 39703, 39709, 39719, 39727, 39733,
496 39749, 39761, 39769, 39779, 39791, 39799, 39821, 39827, 39829,
497 39839, 39841, 39847, 39857, 39863, 39869, 39877, 39883, 39887,
498 39901, 39929, 39937, 39953, 39971, 39979, 39983, 39989, 40009,
499 40013, 40031, 40037, 40039, 40063, 40087, 40093, 40099, 40111,
500 40123, 40127, 40129, 40151, 40153, 40163, 40169, 40177, 40189,
501 40193, 40213, 40231, 40237, 40241, 40253, 40277, 40283, 40289,
502 40343, 40351, 40357, 40361, 40387, 40423, 40427, 40429, 40433,
503 40459, 40471, 40483, 40487, 40493, 40499, 40507, 40519, 40529,
504 40531, 40543, 40559, 40577, 40583, 40591, 40597, 40609, 40627,
505 40637, 40639, 40693, 40697, 40699, 40709, 40739, 40751, 40759,
506 40763, 40771, 40787, 40801, 40813, 40819, 40823, 40829, 40841,
507 40847, 40849, 40853, 40867, 40879, 40883, 40897, 40903, 40927,
508 40933, 40939, 40949, 40961, 40973, 40993, 41011, 41017, 41023,
509 41039, 41047, 41051, 41057, 41077, 41081, 41113, 41117, 41131,
510 41141, 41143, 41149, 41161, 41177, 41179, 41183, 41189, 41201,
511 41203, 41213, 41221, 41227, 41231, 41233, 41243, 41257, 41263,
512 41269, 41281, 41299, 41333, 41341, 41351, 41357, 41381, 41387,
513 41389, 41399, 41411, 41413, 41443, 41453, 41467, 41479, 41491,
514 41507, 41513, 41519, 41521, 41539, 41543, 41549, 41579, 41593,
515 41597, 41603, 41609, 41611, 41617, 41621, 41627, 41641, 41647,
516 41651, 41659, 41669, 41681, 41687, 41719, 41729, 41737, 41759,
517 41761, 41771, 41777, 41801, 41809, 41813, 41843, 41849, 41851,
518 41863, 41879, 41887, 41893, 41897, 41903, 41911, 41927, 41941,
519 41947, 41953, 41957, 41959, 41969, 41981, 41983, 41999, 42013,
520 42017, 42019, 42023, 42043, 42061, 42071, 42073, 42083, 42089,
521 42101, 42131, 42139, 42157, 42169, 42179, 42181, 42187, 42193,
522 42197, 42209, 42221, 42223, 42227, 42239, 42257, 42281, 42283,
523 42293, 42299, 42307, 42323, 42331, 42337, 42349, 42359, 42373,
524 42379, 42391, 42397, 42403, 42407, 42409, 42433, 42437, 42443,
525 42451, 42457, 42461, 42463, 42467, 42473, 42487, 42491, 42499,
526 42509, 42533, 42557, 42569, 42571, 42577, 42589, 42611, 42641,
527 42643, 42649, 42667, 42677, 42683, 42689, 42697, 42701, 42703,
528 42709, 42719, 42727, 42737, 42743, 42751, 42767, 42773, 42787,
529 42793, 42797, 42821, 42829, 42839, 42841, 42853, 42859, 42863,
530 42899, 42901, 42923, 42929, 42937, 42943, 42953, 42961, 42967,
531 42979, 42989, 43003, 43013, 43019, 43037, 43049, 43051, 43063,
532 43067, 43093, 43103, 43117, 43133, 43151, 43159, 43177, 43189,
533 43201, 43207, 43223, 43237, 43261, 43271, 43283, 43291, 43313,
534 43319, 43321, 43331, 43391, 43397, 43399, 43403, 43411, 43427,
535 43441, 43451, 43457, 43481, 43487, 43499, 43517, 43541, 43543,
536 43573, 43577, 43579, 43591, 43597, 43607, 43609, 43613, 43627,
537 43633, 43649, 43651, 43661, 43669, 43691, 43711, 43717, 43721,
538 43753, 43759, 43777, 43781, 43783, 43787, 43789, 43793, 43801,
539 43853, 43867, 43889, 43891, 43913, 43933, 43943, 43951, 43961,
540 43963, 43969, 43973, 43987, 43991, 43997, 44017, 44021, 44027,
541 44029, 44041, 44053, 44059, 44071, 44087, 44089, 44101, 44111,
542 44119, 44123, 44129, 44131, 44159, 44171, 44179, 44189, 44201,
543 44203, 44207, 44221, 44249, 44257, 44263, 44267, 44269, 44273,
544 44279, 44281, 44293, 44351, 44357, 44371, 44381, 44383, 44389,
545 44417, 44449, 44453, 44483, 44491, 44497, 44501, 44507, 44519,
546 44531, 44533, 44537, 44543, 44549, 44563, 44579, 44587, 44617,
547 44621, 44623, 44633, 44641, 44647, 44651, 44657, 44683, 44687,
548 44699, 44701, 44711, 44729, 44741, 44753, 44771, 44773, 44777,
549 44789, 44797, 44809, 44819, 44839, 44843, 44851, 44867, 44879,
550 44887, 44893, 44909, 44917, 44927, 44939, 44953, 44959, 44963,
551 44971, 44983, 44987, 45007, 45013, 45053, 45061, 45077, 45083,
552 45119, 45121, 45127, 45131, 45137, 45139, 45161, 45179, 45181,
553 45191, 45197, 45233, 45247, 45259, 45263, 45281, 45289, 45293,
554 45307, 45317, 45319, 45329, 45337, 45341, 45343, 45361, 45377,
555 45389, 45403, 45413, 45427, 45433, 45439, 45481, 45491, 45497,
556 45503, 45523, 45533, 45541, 45553, 45557, 45569, 45587, 45589,
557 45599, 45613, 45631, 45641, 45659, 45667, 45673, 45677, 45691,
558 45697, 45707, 45737, 45751, 45757, 45763, 45767, 45779, 45817,
559 45821, 45823, 45827, 45833, 45841, 45853, 45863, 45869, 45887,
560 45893, 45943, 45949, 45953, 45959, 45971, 45979, 45989, 46021,
561 46027, 46049, 46051, 46061, 46073, 46091, 46093, 46099, 46103,
562 46133, 46141, 46147, 46153, 46171, 46181, 46183, 46187, 46199,
563 46219, 46229, 46237, 46261, 46271, 46273, 46279, 46301, 46307,
564 46309, 46327, 46337, 46349, 46351, 46381, 46399, 46411, 46439,
565 46441, 46447, 46451, 46457, 46471, 46477, 46489, 46499, 46507,
566 46511, 46523, 46549, 46559, 46567, 46573, 46589, 46591, 46601,
567 46619, 46633, 46639, 46643, 46649, 46663, 46679, 46681, 46687,
568 46691, 46703, 46723, 46727, 46747, 46751, 46757, 46769, 46771,
569 46807, 46811, 46817, 46819, 46829, 46831, 46853, 46861, 46867,
570 46877, 46889, 46901, 46919, 46933, 46957, 46993, 46997, 47017,
571 47041, 47051, 47057, 47059, 47087, 47093, 47111, 47119, 47123,
572 47129, 47137, 47143, 47147, 47149, 47161, 47189, 47207, 47221,
573 47237, 47251, 47269, 47279, 47287, 47293, 47297, 47303, 47309,
574 47317, 47339, 47351, 47353, 47363, 47381, 47387, 47389, 47407,
575 47417, 47419, 47431, 47441, 47459, 47491, 47497, 47501, 47507,
576 47513, 47521, 47527, 47533, 47543, 47563, 47569, 47581, 47591,
577 47599, 47609, 47623, 47629, 47639, 47653, 47657, 47659, 47681,
578 47699, 47701, 47711, 47713, 47717, 47737, 47741, 47743, 47777,
579 47779, 47791, 47797, 47807, 47809, 47819, 47837, 47843, 47857,
580 47869, 47881, 47903, 47911, 47917, 47933, 47939, 47947, 47951,
581 47963, 47969, 47977, 47981, 48017, 48023, 48029, 48049, 48073,
582 48079, 48091, 48109, 48119, 48121, 48131, 48157, 48163, 48179,
583 48187, 48193, 48197, 48221, 48239, 48247, 48259, 48271, 48281,
584 48299, 48311, 48313, 48337, 48341, 48353, 48371, 48383, 48397,
585 48407, 48409, 48413, 48437, 48449, 48463, 48473, 48479, 48481,
586 48487, 48491, 48497, 48523, 48527, 48533, 48539, 48541, 48563,
587 48571, 48589, 48593, 48611, 48619, 48623, 48647, 48649, 48661,
588 48673, 48677, 48679, 48731, 48733, 48751, 48757, 48761, 48767,
589 48779, 48781, 48787, 48799, 48809, 48817, 48821, 48823, 48847,
590 48857, 48859, 48869, 48871, 48883, 48889, 48907, 48947, 48953,
591 48973, 48989, 48991, 49003, 49009, 49019, 49031, 49033, 49037,
592 49043, 49057, 49069, 49081, 49103, 49109, 49117, 49121, 49123,
593 49139, 49157, 49169, 49171, 49177, 49193, 49199, 49201, 49207,
594 49211, 49223, 49253, 49261, 49277, 49279, 49297, 49307, 49331,
595 49333, 49339, 49363, 49367, 49369, 49391, 49393, 49409, 49411,
596 49417, 49429, 49433, 49451, 49459, 49463, 49477, 49481, 49499,
597 49523, 49529, 49531, 49537, 49547, 49549, 49559, 49597, 49603,
598 49613, 49627, 49633, 49639, 49663, 49667, 49669, 49681, 49697,
599 49711, 49727, 49739, 49741, 49747, 49757, 49783, 49787, 49789,
600 49801, 49807, 49811, 49823, 49831, 49843, 49853, 49871, 49877,
601 49891, 49919, 49921, 49927, 49937, 49939, 49943, 49957, 49991,
602 49993, 49999, 50021, 50023, 50033, 50047, 50051, 50053, 50069,
603 50077, 50087, 50093, 50101, 50111, 50119, 50123, 50129, 50131,
604 50147, 50153, 50159, 50177, 50207, 50221, 50227, 50231, 50261,
605 50263, 50273, 50287, 50291, 50311, 50321, 50329, 50333, 50341,
606 50359, 50363, 50377, 50383, 50387, 50411, 50417, 50423, 50441,
607 50459, 50461, 50497, 50503, 50513, 50527, 50539, 50543, 50549,
608 50551, 50581, 50587, 50591, 50593, 50599, 50627, 50647, 50651,
609 50671, 50683, 50707, 50723, 50741, 50753, 50767, 50773, 50777,
610 50789, 50821, 50833, 50839, 50849, 50857, 50867, 50873, 50891,
611 50893, 50909, 50923, 50929, 50951, 50957, 50969, 50971, 50989,
612 50993, 51001, 51031, 51043, 51047, 51059, 51061, 51071, 51109,
613 51131, 51133, 51137, 51151, 51157, 51169, 51193, 51197, 51199,
614 51203, 51217, 51229, 51239, 51241, 51257, 51263, 51283, 51287,
615 51307, 51329, 51341, 51343, 51347, 51349, 51361, 51383, 51407,
616 51413, 51419, 51421, 51427, 51431, 51437, 51439, 51449, 51461,
617 51473, 51479, 51481, 51487, 51503, 51511, 51517, 51521, 51539,
618 51551, 51563, 51577, 51581, 51593, 51599, 51607, 51613, 51631,
619 51637, 51647, 51659, 51673, 51679, 51683, 51691, 51713, 51719,
620 51721, 51749, 51767, 51769, 51787, 51797, 51803, 51817, 51827,
621 51829, 51839, 51853, 51859, 51869, 51871, 51893, 51899, 51907,
622 51913, 51929, 51941, 51949, 51971, 51973, 51977, 51991, 52009,
623 52021, 52027, 52051, 52057, 52067, 52069, 52081, 52103, 52121,
624 52127, 52147, 52153, 52163, 52177, 52181, 52183, 52189, 52201,
625 52223, 52237, 52249, 52253, 52259, 52267, 52289, 52291, 52301,
626 52313, 52321, 52361, 52363, 52369, 52379, 52387, 52391, 52433,
627 52453, 52457, 52489, 52501, 52511, 52517, 52529, 52541, 52543,
628 52553, 52561, 52567, 52571, 52579, 52583, 52609, 52627, 52631,
629 52639, 52667, 52673, 52691, 52697, 52709, 52711, 52721, 52727,
630 52733, 52747, 52757, 52769, 52783, 52807, 52813, 52817, 52837,
631 52859, 52861, 52879, 52883, 52889, 52901, 52903, 52919, 52937,
632 52951, 52957, 52963, 52967, 52973, 52981, 52999, 53003, 53017,
633 53047, 53051, 53069, 53077, 53087, 53089, 53093, 53101, 53113,
634 53117, 53129, 53147, 53149, 53161, 53171, 53173, 53189, 53197,
635 53201, 53231, 53233, 53239, 53267, 53269, 53279, 53281, 53299,
636 53309, 53323, 53327, 53353, 53359, 53377, 53381, 53401, 53407,
637 53411, 53419, 53437, 53441, 53453, 53479, 53503, 53507, 53527,
638 53549, 53551, 53569, 53591, 53593, 53597, 53609, 53611, 53617,
639 53623, 53629, 53633, 53639, 53653, 53657, 53681, 53693, 53699,
640 53717, 53719, 53731, 53759, 53773, 53777, 53783, 53791, 53813,
641 53819, 53831, 53849, 53857, 53861, 53881, 53887, 53891, 53897,
642 53899, 53917, 53923, 53927, 53939, 53951, 53959, 53987, 53993,
643 54001, 54011, 54013, 54037, 54049, 54059, 54083, 54091, 54101,
644 54121, 54133, 54139, 54151, 54163, 54167, 54181, 54193, 54217,
645 54251, 54269, 54277, 54287, 54293, 54311, 54319, 54323, 54331,
646 54347, 54361, 54367, 54371, 54377, 54401, 54403, 54409, 54413,
647 54419, 54421, 54437, 54443, 54449, 54469, 54493, 54497, 54499,
648 54503, 54517, 54521, 54539, 54541, 54547, 54559, 54563, 54577,
649 54581, 54583, 54601, 54617, 54623, 54629, 54631, 54647, 54667,
650 54673, 54679, 54709, 54713, 54721, 54727, 54751, 54767, 54773,
651 54779, 54787, 54799, 54829, 54833, 54851, 54869, 54877, 54881,
652 54907, 54917, 54919, 54941, 54949, 54959, 54973, 54979, 54983,
653 55001, 55009, 55021, 55049, 55051, 55057, 55061, 55073, 55079,
654 55103, 55109, 55117, 55127, 55147, 55163, 55171, 55201, 55207,
655 55213, 55217, 55219, 55229, 55243, 55249, 55259, 55291, 55313,
656 55331, 55333, 55337, 55339, 55343, 55351, 55373, 55381, 55399,
657 55411, 55439, 55441, 55457, 55469, 55487, 55501, 55511, 55529,
658 55541, 55547, 55579, 55589, 55603, 55609, 55619, 55621, 55631,
659 55633, 55639, 55661, 55663, 55667, 55673, 55681, 55691, 55697,
660 55711, 55717, 55721, 55733, 55763, 55787, 55793, 55799, 55807,
661 55813, 55817, 55819, 55823, 55829, 55837, 55843, 55849, 55871,
662 55889, 55897, 55901, 55903, 55921, 55927, 55931, 55933, 55949,
663 55967, 55987, 55997, 56003, 56009, 56039, 56041, 56053, 56081,
664 56087, 56093, 56099, 56101, 56113, 56123, 56131, 56149, 56167,
665 56171, 56179, 56197, 56207, 56209, 56237, 56239, 56249, 56263,
666 56267, 56269, 56299, 56311, 56333, 56359, 56369, 56377, 56383,
667 56393, 56401, 56417, 56431, 56437, 56443, 56453, 56467, 56473,
668 56477, 56479, 56489, 56501, 56503, 56509, 56519, 56527, 56531,
669 56533, 56543, 56569, 56591, 56597, 56599, 56611, 56629, 56633,
670 56659, 56663, 56671, 56681, 56687, 56701, 56711, 56713, 56731,
671 56737, 56747, 56767, 56773, 56779, 56783, 56807, 56809, 56813,
672 56821, 56827, 56843, 56857, 56873, 56891, 56893, 56897, 56909,
673 56911, 56921, 56923, 56929, 56941, 56951, 56957, 56963, 56983,
674 56989, 56993, 56999, 57037, 57041, 57047, 57059, 57073, 57077,
675 57089, 57097, 57107, 57119, 57131, 57139, 57143, 57149, 57163,
676 57173, 57179, 57191, 57193, 57203, 57221, 57223, 57241, 57251,
677 57259, 57269, 57271, 57283, 57287, 57301, 57329, 57331, 57347,
678 57349, 57367, 57373, 57383, 57389, 57397, 57413, 57427, 57457,
679 57467, 57487, 57493, 57503, 57527, 57529, 57557, 57559, 57571,
680 57587, 57593, 57601, 57637, 57641, 57649, 57653, 57667, 57679,
681 57689, 57697, 57709, 57713, 57719, 57727, 57731, 57737, 57751,
682 57773, 57781, 57787, 57791, 57793, 57803, 57809, 57829, 57839,
683 57847, 57853, 57859, 57881, 57899, 57901, 57917, 57923, 57943,
684 57947, 57973, 57977, 57991, 58013, 58027, 58031, 58043, 58049,
685 58057, 58061, 58067, 58073, 58099, 58109, 58111, 58129, 58147,
686 58151, 58153, 58169, 58171, 58189, 58193, 58199, 58207, 58211,
687 58217, 58229, 58231, 58237, 58243, 58271, 58309, 58313, 58321,
688 58337, 58363, 58367, 58369, 58379, 58391, 58393, 58403, 58411,
689 58417, 58427, 58439, 58441, 58451, 58453, 58477, 58481, 58511,
690 58537, 58543, 58549, 58567, 58573, 58579, 58601, 58603, 58613,
691 58631, 58657, 58661, 58679, 58687, 58693, 58699, 58711, 58727,
692 58733, 58741, 58757, 58763, 58771, 58787, 58789, 58831, 58889,
693 58897, 58901, 58907, 58909, 58913, 58921, 58937, 58943, 58963,
694 58967, 58979, 58991, 58997, 59009, 59011, 59021, 59023, 59029,
695 59051, 59053, 59063, 59069, 59077, 59083, 59093, 59107, 59113,
696 59119, 59123, 59141, 59149, 59159, 59167, 59183, 59197, 59207,
697 59209, 59219, 59221, 59233, 59239, 59243, 59263, 59273, 59281,
698 59333, 59341, 59351, 59357, 59359, 59369, 59377, 59387, 59393,
699 59399, 59407, 59417, 59419, 59441, 59443, 59447, 59453, 59467,
700 59471, 59473, 59497, 59509, 59513, 59539, 59557, 59561, 59567,
701 59581, 59611, 59617, 59621, 59627, 59629, 59651, 59659, 59663,
702 59669, 59671, 59693, 59699, 59707, 59723, 59729, 59743, 59747,
703 59753, 59771, 59779, 59791, 59797, 59809, 59833, 59863, 59879,
704 59887, 59921, 59929, 59951, 59957, 59971, 59981, 59999, 60013,
705 60017, 60029, 60037, 60041, 60077, 60083, 60089, 60091, 60101,
706 60103, 60107, 60127, 60133, 60139, 60149, 60161, 60167, 60169,
707 60209, 60217, 60223, 60251, 60257, 60259, 60271, 60289, 60293,
708 60317, 60331, 60337, 60343, 60353, 60373, 60383, 60397, 60413,
709 60427, 60443, 60449, 60457, 60493, 60497, 60509, 60521, 60527,
710 60539, 60589, 60601, 60607, 60611, 60617, 60623, 60631, 60637,
711 60647, 60649, 60659, 60661, 60679, 60689, 60703, 60719, 60727,
712 60733, 60737, 60757, 60761, 60763, 60773, 60779, 60793, 60811,
713 60821, 60859, 60869, 60887, 60889, 60899, 60901, 60913, 60917,
714 60919, 60923, 60937, 60943, 60953, 60961, 61001, 61007, 61027,
715 61031, 61043, 61051, 61057, 61091, 61099, 61121, 61129, 61141,
716 61151, 61153, 61169, 61211, 61223, 61231, 61253, 61261, 61283,
717 61291, 61297, 61331, 61333, 61339, 61343, 61357, 61363, 61379,
718 61381, 61403, 61409, 61417, 61441, 61463, 61469, 61471, 61483,
719 61487, 61493, 61507, 61511, 61519, 61543, 61547, 61553, 61559,
720 61561, 61583, 61603, 61609, 61613, 61627, 61631, 61637, 61643,
721 61651, 61657, 61667, 61673, 61681, 61687, 61703, 61717, 61723,
722 61729, 61751, 61757, 61781, 61813, 61819, 61837, 61843, 61861,
723 61871, 61879, 61909, 61927, 61933, 61949, 61961, 61967, 61979,
724 61981, 61987, 61991, 62003, 62011, 62017, 62039, 62047, 62053,
725 62057, 62071, 62081, 62099, 62119, 62129, 62131, 62137, 62141,
726 62143, 62171, 62189, 62191, 62201, 62207, 62213, 62219, 62233,
727 62273, 62297, 62299, 62303, 62311, 62323, 62327, 62347, 62351,
728 62383, 62401, 62417, 62423, 62459, 62467, 62473, 62477, 62483,
729 62497, 62501, 62507, 62533, 62539, 62549, 62563, 62581, 62591,
730 62597, 62603, 62617, 62627, 62633, 62639, 62653, 62659, 62683,
731 62687, 62701, 62723, 62731, 62743, 62753, 62761, 62773, 62791,
732 62801, 62819, 62827, 62851, 62861, 62869, 62873, 62897, 62903,
733 62921, 62927, 62929, 62939, 62969, 62971, 62981, 62983, 62987,
734 62989, 63029, 63031, 63059, 63067, 63073, 63079, 63097, 63103,
735 63113, 63127, 63131, 63149, 63179, 63197, 63199, 63211, 63241,
736 63247, 63277, 63281, 63299, 63311, 63313, 63317, 63331, 63337,
737 63347, 63353, 63361, 63367, 63377, 63389, 63391, 63397, 63409,
738 63419, 63421, 63439, 63443, 63463, 63467, 63473, 63487, 63493,
739 63499, 63521, 63527, 63533, 63541, 63559, 63577, 63587, 63589,
740 63599, 63601, 63607, 63611, 63617, 63629, 63647, 63649, 63659,
741 63667, 63671, 63689, 63691, 63697, 63703, 63709, 63719, 63727,
742 63737, 63743, 63761, 63773, 63781, 63793, 63799, 63803, 63809,
743 63823, 63839, 63841, 63853, 63857, 63863, 63901, 63907, 63913,
744 63929, 63949, 63977, 63997, 64007, 64013, 64019, 64033, 64037,
745 64063, 64067, 64081, 64091, 64109, 64123, 64151, 64153, 64157,
746 64171, 64187, 64189, 64217, 64223, 64231, 64237, 64271, 64279,
747 64283, 64301, 64303, 64319, 64327, 64333, 64373, 64381, 64399,
748 64403, 64433, 64439, 64451, 64453, 64483, 64489, 64499, 64513,
749 64553, 64567, 64577, 64579, 64591, 64601, 64609, 64613, 64621,
750 64627, 64633, 64661, 64663, 64667, 64679, 64693, 64709, 64717,
751 64747, 64763, 64781, 64783, 64793, 64811, 64817, 64849, 64853,
752 64871, 64877, 64879, 64891, 64901, 64919, 64921, 64927, 64937,
753 64951, 64969, 64997, 65003, 65011, 65027, 65029, 65033, 65053,
754 65063, 65071, 65089, 65099, 65101, 65111, 65119, 65123, 65129,
755 65141, 65147, 65167, 65171, 65173, 65179, 65183, 65203, 65213,
756 65239, 65257, 65267, 65269, 65287, 65293, 65309, 65323, 65327,
757 65353, 65357, 65371, 65381, 65393, 65407, 65413, 65419, 65423,
758 65437, 65447, 65449, 65479, 65497, 65519, 65521, 65537, 65539
762 _hash_prime(unsigned long start)
766 /* Range-check the starting number */
769 else if (start > MAX_PRIME) /* largest 32-bit prime */
772 /* OK, force the number to the next highest odd (the |= 1), then
773 * check sequential odd numbers (the += 2)...
775 for (start |= 1; ; start += 2)
776 for (i = 0; ; i++) /* Walk through the table of 16-bit primes */
777 if (!(start % primes[i])) /* it divided evenly, so skip to the next */
779 else if ((start / primes[i]) < primes[i])
780 return start; /* we've checked everything now, so it's prime */