60 #define NUMPRIMES 2048
64 static const unsigned int primes[
NUMPRIMES]=
66 2, 3, 5, 7, 11, 13, 17, 19,
67 23, 29, 31, 37, 41, 43, 47, 53,
68 59, 61, 67, 71, 73, 79, 83, 89,
69 97, 101, 103, 107, 109, 113, 127, 131,
70 137, 139, 149, 151, 157, 163, 167, 173,
71 179, 181, 191, 193, 197, 199, 211, 223,
72 227, 229, 233, 239, 241, 251,
75 269, 271, 277, 281, 283, 293, 307, 311,
76 313, 317, 331, 337, 347, 349, 353, 359,
77 367, 373, 379, 383, 389, 397, 401, 409,
78 419, 421, 431, 433, 439, 443, 449, 457,
79 461, 463, 467, 479, 487, 491, 499, 503,
80 509, 521, 523, 541, 547, 557, 563, 569,
81 571, 577, 587, 593, 599, 601, 607, 613,
82 617, 619, 631, 641, 643, 647, 653, 659,
83 661, 673, 677, 683, 691, 701, 709, 719,
84 727, 733, 739, 743, 751, 757, 761, 769,
85 773, 787, 797, 809, 811, 821, 823, 827,
86 829, 839, 853, 857, 859, 863, 877, 881,
87 883, 887, 907, 911, 919, 929, 937, 941,
88 947, 953, 967, 971, 977, 983, 991, 997,
89 1009,1013,1019,1021,1031,1033,1039,1049,
90 1051,1061,1063,1069,1087,1091,1093,1097,
91 1103,1109,1117,1123,1129,1151,1153,1163,
92 1171,1181,1187,1193,1201,1213,1217,1223,
93 1229,1231,1237,1249,1259,1277,1279,1283,
94 1289,1291,1297,1301,1303,1307,1319,1321,
95 1327,1361,1367,1373,1381,1399,1409,1423,
96 1427,1429,1433,1439,1447,1451,1453,1459,
97 1471,1481,1483,1487,1489,1493,1499,1511,
98 1523,1531,1543,1549,1553,1559,1567,1571,
99 1579,1583,1597,1601,1607,1609,1613,1619,
100 1621,1627,1637,1657,1663,1667,1669,1693,
101 1697,1699,1709,1721,1723,1733,1741,1747,
102 1753,1759,1777,1783,1787,1789,1801,1811,
103 1823,1831,1847,1861,1867,1871,1873,1877,
104 1879,1889,1901,1907,1913,1931,1933,1949,
105 1951,1973,1979,1987,1993,1997,1999,2003,
106 2011,2017,2027,2029,2039,2053,2063,2069,
107 2081,2083,2087,2089,2099,2111,2113,2129,
108 2131,2137,2141,2143,2153,2161,2179,2203,
109 2207,2213,2221,2237,2239,2243,2251,2267,
110 2269,2273,2281,2287,2293,2297,2309,2311,
111 2333,2339,2341,2347,2351,2357,2371,2377,
112 2381,2383,2389,2393,2399,2411,2417,2423,
113 2437,2441,2447,2459,2467,2473,2477,2503,
114 2521,2531,2539,2543,2549,2551,2557,2579,
115 2591,2593,2609,2617,2621,2633,2647,2657,
116 2659,2663,2671,2677,2683,2687,2689,2693,
117 2699,2707,2711,2713,2719,2729,2731,2741,
118 2749,2753,2767,2777,2789,2791,2797,2801,
119 2803,2819,2833,2837,2843,2851,2857,2861,
120 2879,2887,2897,2903,2909,2917,2927,2939,
121 2953,2957,2963,2969,2971,2999,3001,3011,
122 3019,3023,3037,3041,3049,3061,3067,3079,
123 3083,3089,3109,3119,3121,3137,3163,3167,
124 3169,3181,3187,3191,3203,3209,3217,3221,
125 3229,3251,3253,3257,3259,3271,3299,3301,
126 3307,3313,3319,3323,3329,3331,3343,3347,
127 3359,3361,3371,3373,3389,3391,3407,3413,
128 3433,3449,3457,3461,3463,3467,3469,3491,
129 3499,3511,3517,3527,3529,3533,3539,3541,
130 3547,3557,3559,3571,3581,3583,3593,3607,
131 3613,3617,3623,3631,3637,3643,3659,3671,
132 3673,3677,3691,3697,3701,3709,3719,3727,
133 3733,3739,3761,3767,3769,3779,3793,3797,
134 3803,3821,3823,3833,3847,3851,3853,3863,
135 3877,3881,3889,3907,3911,3917,3919,3923,
136 3929,3931,3943,3947,3967,3989,4001,4003,
137 4007,4013,4019,4021,4027,4049,4051,4057,
138 4073,4079,4091,4093,4099,4111,4127,4129,
139 4133,4139,4153,4157,4159,4177,4201,4211,
140 4217,4219,4229,4231,4241,4243,4253,4259,
141 4261,4271,4273,4283,4289,4297,4327,4337,
142 4339,4349,4357,4363,4373,4391,4397,4409,
143 4421,4423,4441,4447,4451,4457,4463,4481,
144 4483,4493,4507,4513,4517,4519,4523,4547,
145 4549,4561,4567,4583,4591,4597,4603,4621,
146 4637,4639,4643,4649,4651,4657,4663,4673,
147 4679,4691,4703,4721,4723,4729,4733,4751,
148 4759,4783,4787,4789,4793,4799,4801,4813,
149 4817,4831,4861,4871,4877,4889,4903,4909,
150 4919,4931,4933,4937,4943,4951,4957,4967,
151 4969,4973,4987,4993,4999,5003,5009,5011,
152 5021,5023,5039,5051,5059,5077,5081,5087,
153 5099,5101,5107,5113,5119,5147,5153,5167,
154 5171,5179,5189,5197,5209,5227,5231,5233,
155 5237,5261,5273,5279,5281,5297,5303,5309,
156 5323,5333,5347,5351,5381,5387,5393,5399,
157 5407,5413,5417,5419,5431,5437,5441,5443,
158 5449,5471,5477,5479,5483,5501,5503,5507,
159 5519,5521,5527,5531,5557,5563,5569,5573,
160 5581,5591,5623,5639,5641,5647,5651,5653,
161 5657,5659,5669,5683,5689,5693,5701,5711,
162 5717,5737,5741,5743,5749,5779,5783,5791,
163 5801,5807,5813,5821,5827,5839,5843,5849,
164 5851,5857,5861,5867,5869,5879,5881,5897,
165 5903,5923,5927,5939,5953,5981,5987,6007,
166 6011,6029,6037,6043,6047,6053,6067,6073,
167 6079,6089,6091,6101,6113,6121,6131,6133,
168 6143,6151,6163,6173,6197,6199,6203,6211,
169 6217,6221,6229,6247,6257,6263,6269,6271,
170 6277,6287,6299,6301,6311,6317,6323,6329,
171 6337,6343,6353,6359,6361,6367,6373,6379,
172 6389,6397,6421,6427,6449,6451,6469,6473,
173 6481,6491,6521,6529,6547,6551,6553,6563,
174 6569,6571,6577,6581,6599,6607,6619,6637,
175 6653,6659,6661,6673,6679,6689,6691,6701,
176 6703,6709,6719,6733,6737,6761,6763,6779,
177 6781,6791,6793,6803,6823,6827,6829,6833,
178 6841,6857,6863,6869,6871,6883,6899,6907,
179 6911,6917,6947,6949,6959,6961,6967,6971,
180 6977,6983,6991,6997,7001,7013,7019,7027,
181 7039,7043,7057,7069,7079,7103,7109,7121,
182 7127,7129,7151,7159,7177,7187,7193,7207,
183 7211,7213,7219,7229,7237,7243,7247,7253,
184 7283,7297,7307,7309,7321,7331,7333,7349,
185 7351,7369,7393,7411,7417,7433,7451,7457,
186 7459,7477,7481,7487,7489,7499,7507,7517,
187 7523,7529,7537,7541,7547,7549,7559,7561,
188 7573,7577,7583,7589,7591,7603,7607,7621,
189 7639,7643,7649,7669,7673,7681,7687,7691,
190 7699,7703,7717,7723,7727,7741,7753,7757,
191 7759,7789,7793,7817,7823,7829,7841,7853,
192 7867,7873,7877,7879,7883,7901,7907,7919,
193 7927,7933,7937,7949,7951,7963,7993,8009,
194 8011,8017,8039,8053,8059,8069,8081,8087,
195 8089,8093,8101,8111,8117,8123,8147,8161,
196 8167,8171,8179,8191,8209,8219,8221,8231,
197 8233,8237,8243,8263,8269,8273,8287,8291,
198 8293,8297,8311,8317,8329,8353,8363,8369,
199 8377,8387,8389,8419,8423,8429,8431,8443,
200 8447,8461,8467,8501,8513,8521,8527,8537,
201 8539,8543,8563,8573,8581,8597,8599,8609,
202 8623,8627,8629,8641,8647,8663,8669,8677,
203 8681,8689,8693,8699,8707,8713,8719,8731,
204 8737,8741,8747,8753,8761,8779,8783,8803,
205 8807,8819,8821,8831,8837,8839,8849,8861,
206 8863,8867,8887,8893,8923,8929,8933,8941,
207 8951,8963,8969,8971,8999,9001,9007,9011,
208 9013,9029,9041,9043,9049,9059,9067,9091,
209 9103,9109,9127,9133,9137,9151,9157,9161,
210 9173,9181,9187,9199,9203,9209,9221,9227,
211 9239,9241,9257,9277,9281,9283,9293,9311,
212 9319,9323,9337,9341,9343,9349,9371,9377,
213 9391,9397,9403,9413,9419,9421,9431,9433,
214 9437,9439,9461,9463,9467,9473,9479,9491,
215 9497,9511,9521,9533,9539,9547,9551,9587,
216 9601,9613,9619,9623,9629,9631,9643,9649,
217 9661,9677,9679,9689,9697,9719,9721,9733,
218 9739,9743,9749,9767,9769,9781,9787,9791,
219 9803,9811,9817,9829,9833,9839,9851,9857,
220 9859,9871,9883,9887,9901,9907,9923,9929,
221 9931,9941,9949,9967,9973,10007,10009,10037,
222 10039,10061,10067,10069,10079,10091,10093,10099,
223 10103,10111,10133,10139,10141,10151,10159,10163,
224 10169,10177,10181,10193,10211,10223,10243,10247,
225 10253,10259,10267,10271,10273,10289,10301,10303,
226 10313,10321,10331,10333,10337,10343,10357,10369,
227 10391,10399,10427,10429,10433,10453,10457,10459,
228 10463,10477,10487,10499,10501,10513,10529,10531,
229 10559,10567,10589,10597,10601,10607,10613,10627,
230 10631,10639,10651,10657,10663,10667,10687,10691,
231 10709,10711,10723,10729,10733,10739,10753,10771,
232 10781,10789,10799,10831,10837,10847,10853,10859,
233 10861,10867,10883,10889,10891,10903,10909,10937,
234 10939,10949,10957,10973,10979,10987,10993,11003,
235 11027,11047,11057,11059,11069,11071,11083,11087,
236 11093,11113,11117,11119,11131,11149,11159,11161,
237 11171,11173,11177,11197,11213,11239,11243,11251,
238 11257,11261,11273,11279,11287,11299,11311,11317,
239 11321,11329,11351,11353,11369,11383,11393,11399,
240 11411,11423,11437,11443,11447,11467,11471,11483,
241 11489,11491,11497,11503,11519,11527,11549,11551,
242 11579,11587,11593,11597,11617,11621,11633,11657,
243 11677,11681,11689,11699,11701,11717,11719,11731,
244 11743,11777,11779,11783,11789,11801,11807,11813,
245 11821,11827,11831,11833,11839,11863,11867,11887,
246 11897,11903,11909,11923,11927,11933,11939,11941,
247 11953,11959,11969,11971,11981,11987,12007,12011,
248 12037,12041,12043,12049,12071,12073,12097,12101,
249 12107,12109,12113,12119,12143,12149,12157,12161,
250 12163,12197,12203,12211,12227,12239,12241,12251,
251 12253,12263,12269,12277,12281,12289,12301,12323,
252 12329,12343,12347,12373,12377,12379,12391,12401,
253 12409,12413,12421,12433,12437,12451,12457,12473,
254 12479,12487,12491,12497,12503,12511,12517,12527,
255 12539,12541,12547,12553,12569,12577,12583,12589,
256 12601,12611,12613,12619,12637,12641,12647,12653,
257 12659,12671,12689,12697,12703,12713,12721,12739,
258 12743,12757,12763,12781,12791,12799,12809,12821,
259 12823,12829,12841,12853,12889,12893,12899,12907,
260 12911,12917,12919,12923,12941,12953,12959,12967,
261 12973,12979,12983,13001,13003,13007,13009,13033,
262 13037,13043,13049,13063,13093,13099,13103,13109,
263 13121,13127,13147,13151,13159,13163,13171,13177,
264 13183,13187,13217,13219,13229,13241,13249,13259,
265 13267,13291,13297,13309,13313,13327,13331,13337,
266 13339,13367,13381,13397,13399,13411,13417,13421,
267 13441,13451,13457,13463,13469,13477,13487,13499,
268 13513,13523,13537,13553,13567,13577,13591,13597,
269 13613,13619,13627,13633,13649,13669,13679,13681,
270 13687,13691,13693,13697,13709,13711,13721,13723,
271 13729,13751,13757,13759,13763,13781,13789,13799,
272 13807,13829,13831,13841,13859,13873,13877,13879,
273 13883,13901,13903,13907,13913,13921,13931,13933,
274 13963,13967,13997,13999,14009,14011,14029,14033,
275 14051,14057,14071,14081,14083,14087,14107,14143,
276 14149,14153,14159,14173,14177,14197,14207,14221,
277 14243,14249,14251,14281,14293,14303,14321,14323,
278 14327,14341,14347,14369,14387,14389,14401,14407,
279 14411,14419,14423,14431,14437,14447,14449,14461,
280 14479,14489,14503,14519,14533,14537,14543,14549,
281 14551,14557,14561,14563,14591,14593,14621,14627,
282 14629,14633,14639,14653,14657,14669,14683,14699,
283 14713,14717,14723,14731,14737,14741,14747,14753,
284 14759,14767,14771,14779,14783,14797,14813,14821,
285 14827,14831,14843,14851,14867,14869,14879,14887,
286 14891,14897,14923,14929,14939,14947,14951,14957,
287 14969,14983,15013,15017,15031,15053,15061,15073,
288 15077,15083,15091,15101,15107,15121,15131,15137,
289 15139,15149,15161,15173,15187,15193,15199,15217,
290 15227,15233,15241,15259,15263,15269,15271,15277,
291 15287,15289,15299,15307,15313,15319,15329,15331,
292 15349,15359,15361,15373,15377,15383,15391,15401,
293 15413,15427,15439,15443,15451,15461,15467,15473,
294 15493,15497,15511,15527,15541,15551,15559,15569,
295 15581,15583,15601,15607,15619,15629,15641,15643,
296 15647,15649,15661,15667,15671,15679,15683,15727,
297 15731,15733,15737,15739,15749,15761,15767,15773,
298 15787,15791,15797,15803,15809,15817,15823,15859,
299 15877,15881,15887,15889,15901,15907,15913,15919,
300 15923,15937,15959,15971,15973,15991,16001,16007,
301 16033,16057,16061,16063,16067,16069,16073,16087,
302 16091,16097,16103,16111,16127,16139,16141,16183,
303 16187,16189,16193,16217,16223,16229,16231,16249,
304 16253,16267,16273,16301,16319,16333,16339,16349,
305 16361,16363,16369,16381,16411,16417,16421,16427,
306 16433,16447,16451,16453,16477,16481,16487,16493,
307 16519,16529,16547,16553,16561,16567,16573,16603,
308 16607,16619,16631,16633,16649,16651,16657,16661,
309 16673,16691,16693,16699,16703,16729,16741,16747,
310 16759,16763,16787,16811,16823,16829,16831,16843,
311 16871,16879,16883,16889,16901,16903,16921,16927,
312 16931,16937,16943,16963,16979,16981,16987,16993,
313 17011,17021,17027,17029,17033,17041,17047,17053,
314 17077,17093,17099,17107,17117,17123,17137,17159,
315 17167,17183,17189,17191,17203,17207,17209,17231,
316 17239,17257,17291,17293,17299,17317,17321,17327,
317 17333,17341,17351,17359,17377,17383,17387,17389,
318 17393,17401,17417,17419,17431,17443,17449,17467,
319 17471,17477,17483,17489,17491,17497,17509,17519,
320 17539,17551,17569,17573,17579,17581,17597,17599,
321 17609,17623,17627,17657,17659,17669,17681,17683,
322 17707,17713,17729,17737,17747,17749,17761,17783,
323 17789,17791,17807,17827,17837,17839,17851,17863,