1 //===-------------------------- 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 15 namespace { 16 17 // handle all next_prime(i) for i in [1, 210), special case 0 18 const 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). 73 const 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 146 size_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 } 474 next: 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 486