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