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