blob: a6bd311ef28f9440badaebe49ce420f6572f6ad5 [file] [log] [blame]
Howard Hinnantc51e1022010-05-11 19:42:16 +00001//===-------------------------- hash.cpp ----------------------------------===//
2//
3// ÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊThe LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include "__hash_table"
11#include "algorithm"
12
13_LIBCPP_BEGIN_NAMESPACE_STD
14
15namespace {
16
17// handle all next_prime(i) for i in [1, 210), special case 0
18const unsigned small_primes[] =
19{
20 0,
21 2,
22 3,
23 5,
24 7,
25 11,
26 13,
27 17,
28 19,
29 23,
30 29,
31 31,
32 37,
33 41,
34 43,
35 47,
36 53,
37 59,
38 61,
39 67,
40 71,
41 73,
42 79,
43 83,
44 89,
45 97,
46 101,
47 103,
48 107,
49 109,
50 113,
51 127,
52 131,
53 137,
54 139,
55 149,
56 151,
57 157,
58 163,
59 167,
60 173,
61 179,
62 181,
63 191,
64 193,
65 197,
66 199,
67 211
68};
69
70// potential primes = 210*k + indices[i], k >= 1
71// these numbers are not divisible by 2, 3, 5 or 7
72// (or any integer 2 <= j <= 10 for that matter).
73const unsigned indices[] =
74{
75 1,
76 11,
77 13,
78 17,
79 19,
80 23,
81 29,
82 31,
83 37,
84 41,
85 43,
86 47,
87 53,
88 59,
89 61,
90 67,
91 71,
92 73,
93 79,
94 83,
95 89,
96 97,
97 101,
98 103,
99 107,
100 109,
101 113,
102 121,
103 127,
104 131,
105 137,
106 139,
107 143,
108 149,
109 151,
110 157,
111 163,
112 167,
113 169,
114 173,
115 179,
116 181,
117 187,
118 191,
119 193,
120 197,
121 199,
122 209
123};
124
125}
126
127// Returns: If n == 0, returns 0. Else returns the lowest prime number that
128// is greater than or equal to n.
129//
130// The algorithm creates a list of small primes, plus an open-ended list of
131// potential primes. All prime numbers are potential prime numbers. However
132// some potential prime numbers are not prime. In an ideal world, all potential
133// prime numbers would be prime. Candiate prime numbers are chosen as the next
134// highest potential prime. Then this number is tested for prime by dividing it
135// by all potential prime numbers less than the sqrt of the candidate.
136//
137// This implementation defines potential primes as those numbers not divisible
138// by 2, 3, 5, and 7. Other (common) implementations define potential primes
139// as those not divisible by 2. A few other implementations define potential
140// primes as those not divisible by 2 or 3. By raising the number of small
141// primes which the potential prime is not divisible by, the set of potential
142// primes more closely approximates the set of prime numbers. And thus there
143// are fewer potential primes to search, and fewer potential primes to divide
144// against.
145
146size_t
147__next_prime(size_t n)
148{
149 const size_t L = 210;
150 const size_t N = sizeof(small_primes) / sizeof(small_primes[0]);
151 // If n is small enough, search in small_primes
152 if (n <= small_primes[N-1])
153 return *std::lower_bound(small_primes, small_primes + N, n);
154 // Else n > largest small_primes
155 // Start searching list of potential primes: L * k0 + indices[in]
156 const size_t M = sizeof(indices) / sizeof(indices[0]);
157 // Select first potential prime >= n
158 // Known a-priori n >= L
159 size_t k0 = n / L;
160 size_t in = std::lower_bound(indices, indices + M, n % L) - indices;
161 n = L * k0 + indices[in];
162 while (true)
163 {
164 // Divide n by all primes or potential primes (i) until:
165 // 1. The division is even, so try next potential prime.
166 // 2. The i > sqrt(n), in which case n is prime.
167 // It is known a-priori that n is not divisible by 2, 3, 5 or 7,
168 // so don't test those (j == 5 -> divide by 11 first). And the
169 // potential primes start with 211, so don't test against the last
170 // small prime.
171 for (size_t j = 5; j < N - 1; ++j)
172 {
173 if (n % small_primes[j] == 0)
174 goto next;
175 if (n / small_primes[j] < small_primes[j])
176 return n;
177 }
178 // n wasn't divisible by small primes, try potential primes
179 {
180 size_t i = 211;
181 while (true)
182 {
183 if (n % i == 0)
184 break;
185 if (n / i < i)
186 return n;
187
188 i += 10;
189 if (n % i == 0)
190 break;
191 if (n / i < i)
192 return n;
193
194 i += 2;
195 if (n % i == 0)
196 break;
197 if (n / i < i)
198 return n;
199
200 i += 4;
201 if (n % i == 0)
202 break;
203 if (n / i < i)
204 return n;
205
206 i += 2;
207 if (n % i == 0)
208 break;
209 if (n / i < i)
210 return n;
211
212 i += 4;
213 if (n % i == 0)
214 break;
215 if (n / i < i)
216 return n;
217
218 i += 6;
219 if (n % i == 0)
220 break;
221 if (n / i < i)
222 return n;
223
224 i += 2;
225 if (n % i == 0)
226 break;
227 if (n / i < i)
228 return n;
229
230 i += 6;
231 if (n % i == 0)
232 break;
233 if (n / i < i)
234 return n;
235
236 i += 4;
237 if (n % i == 0)
238 break;
239 if (n / i < i)
240 return n;
241
242 i += 2;
243 if (n % i == 0)
244 break;
245 if (n / i < i)
246 return n;
247
248 i += 4;
249 if (n % i == 0)
250 break;
251 if (n / i < i)
252 return n;
253
254 i += 6;
255 if (n % i == 0)
256 break;
257 if (n / i < i)
258 return n;
259
260 i += 6;
261 if (n % i == 0)
262 break;
263 if (n / i < i)
264 return n;
265
266 i += 2;
267 if (n % i == 0)
268 break;
269 if (n / i < i)
270 return n;
271
272 i += 6;
273 if (n % i == 0)
274 break;
275 if (n / i < i)
276 return n;
277
278 i += 4;
279 if (n % i == 0)
280 break;
281 if (n / i < i)
282 return n;
283
284 i += 2;
285 if (n % i == 0)
286 break;
287 if (n / i < i)
288 return n;
289
290 i += 6;
291 if (n % i == 0)
292 break;
293 if (n / i < i)
294 return n;
295
296 i += 4;
297 if (n % i == 0)
298 break;
299 if (n / i < i)
300 return n;
301
302 i += 6;
303 if (n % i == 0)
304 break;
305 if (n / i < i)
306 return n;
307
308 i += 8;
309 if (n % i == 0)
310 break;
311 if (n / i < i)
312 return n;
313
314 i += 4;
315 if (n % i == 0)
316 break;
317 if (n / i < i)
318 return n;
319
320 i += 2;
321 if (n % i == 0)
322 break;
323 if (n / i < i)
324 return n;
325
326 i += 4;
327 if (n % i == 0)
328 break;
329 if (n / i < i)
330 return n;
331
332 i += 2;
333 if (n % i == 0)
334 break;
335 if (n / i < i)
336 return n;
337
338 i += 4;
339 if (n % i == 0)
340 break;
341 if (n / i < i)
342 return n;
343
344 i += 8;
345 if (n % i == 0)
346 break;
347 if (n / i < i)
348 return n;
349
350 i += 6;
351 if (n % i == 0)
352 break;
353 if (n / i < i)
354 return n;
355
356 i += 4;
357 if (n % i == 0)
358 break;
359 if (n / i < i)
360 return n;
361
362 i += 6;
363 if (n % i == 0)
364 break;
365 if (n / i < i)
366 return n;
367
368 i += 2;
369 if (n % i == 0)
370 break;
371 if (n / i < i)
372 return n;
373
374 i += 4;
375 if (n % i == 0)
376 break;
377 if (n / i < i)
378 return n;
379
380 i += 6;
381 if (n % i == 0)
382 break;
383 if (n / i < i)
384 return n;
385
386 i += 2;
387 if (n % i == 0)
388 break;
389 if (n / i < i)
390 return n;
391
392 i += 6;
393 if (n % i == 0)
394 break;
395 if (n / i < i)
396 return n;
397
398 i += 6;
399 if (n % i == 0)
400 break;
401 if (n / i < i)
402 return n;
403
404 i += 4;
405 if (n % i == 0)
406 break;
407 if (n / i < i)
408 return n;
409
410 i += 2;
411 if (n % i == 0)
412 break;
413 if (n / i < i)
414 return n;
415
416 i += 4;
417 if (n % i == 0)
418 break;
419 if (n / i < i)
420 return n;
421
422 i += 6;
423 if (n % i == 0)
424 break;
425 if (n / i < i)
426 return n;
427
428 i += 2;
429 if (n % i == 0)
430 break;
431 if (n / i < i)
432 return n;
433
434 i += 6;
435 if (n % i == 0)
436 break;
437 if (n / i < i)
438 return n;
439
440 i += 4;
441 if (n % i == 0)
442 break;
443 if (n / i < i)
444 return n;
445
446 i += 2;
447 if (n % i == 0)
448 break;
449 if (n / i < i)
450 return n;
451
452 i += 4;
453 if (n % i == 0)
454 break;
455 if (n / i < i)
456 return n;
457
458 i += 2;
459 if (n % i == 0)
460 break;
461 if (n / i < i)
462 return n;
463
464 i += 10;
465 if (n % i == 0)
466 break;
467 if (n / i < i)
468 return n;
469
470 // This will loop i to the next "plane" of potential primes
471 i += 2;
472 }
473 }
474next:
475 // n is not prime. Increment n to next potential prime.
476 if (++in == M)
477 {
478 ++k0;
479 in = 0;
480 }
481 n = L * k0 + indices[in];
482 }
483}
484
485_LIBCPP_END_NAMESPACE_STD