| 62 | } |
| 63 | |
| 64 | size_t __next_prime(size_t n) { |
| 65 | const size_t L = 210; |
| 66 | const size_t N = sizeof(small_primes) / sizeof(small_primes[0]); |
| 67 | // If n is small enough, search in small_primes |
| 68 | if (n <= small_primes[N - 1]) |
| 69 | return *std::lower_bound(small_primes, small_primes + N, n); |
| 70 | // Else n > largest small_primes |
| 71 | // Check for overflow |
| 72 | __check_for_overflow(n); |
| 73 | // Start searching list of potential primes: L * k0 + indices[in] |
| 74 | const size_t M = sizeof(indices) / sizeof(indices[0]); |
| 75 | // Select first potential prime >= n |
| 76 | // Known a-priori n >= L |
| 77 | size_t k0 = n / L; |
| 78 | size_t in = static_cast<size_t>(std::lower_bound(indices, indices + M, n - k0 * L) - indices); |
| 79 | n = L * k0 + indices[in]; |
| 80 | while (true) { |
| 81 | // Divide n by all primes or potential primes (i) until: |
| 82 | // 1. The division is even, so try next potential prime. |
| 83 | // 2. The i > sqrt(n), in which case n is prime. |
| 84 | // It is known a-priori that n is not divisible by 2, 3, 5 or 7, |
| 85 | // so don't test those (j == 5 -> divide by 11 first). And the |
| 86 | // potential primes start with 211, so don't test against the last |
| 87 | // small prime. |
| 88 | for (size_t j = 5; j < N - 1; ++j) { |
| 89 | const std::size_t p = small_primes[j]; |
| 90 | const std::size_t q = n / p; |
| 91 | if (q < p) |
| 92 | return n; |
| 93 | if (n == q * p) |
| 94 | goto next; |
| 95 | } |
| 96 | // n wasn't divisible by small primes, try potential primes |
| 97 | { |
| 98 | size_t i = 211; |
| 99 | while (true) { |
| 100 | std::size_t q = n / i; |
| 101 | if (q < i) |
| 102 | return n; |
| 103 | if (n == q * i) |
| 104 | break; |
| 105 | |
| 106 | i += 10; |
| 107 | q = n / i; |
| 108 | if (q < i) |
| 109 | return n; |
| 110 | if (n == q * i) |
| 111 | break; |
| 112 | |
| 113 | i += 2; |
| 114 | q = n / i; |
| 115 | if (q < i) |
| 116 | return n; |
| 117 | if (n == q * i) |
| 118 | break; |
| 119 | |
| 120 | i += 4; |
| 121 | q = n / i; |
nothing calls this directly
no test coverage detected