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