1 /* 2 Copyright (C) 2009 William Hart 3 Copyright (C) 2010, 2013 Fredrik Johansson 4 5 This file is part of FLINT. 6 7 FLINT is free software: you can redistribute it and/or modify it under 8 the terms of the GNU Lesser General Public License (LGPL) as published 9 by the Free Software Foundation; either version 2.1 of the License, or 10 (at your option) any later version. See <http://www.gnu.org/licenses/>. 11 */ 12 13 #include <gmp.h> 14 #include "flint.h" 15 #include "ulong_extras.h" 16 17 extern const unsigned char FLINT_PRIME_PI_ODD_LOOKUP[]; 18 n_prime_pi_bounds(ulong * lo,ulong * hi,mp_limb_t n)19void n_prime_pi_bounds(ulong *lo, ulong *hi, mp_limb_t n) 20 { 21 if (n < FLINT_PRIME_PI_ODD_LOOKUP_CUTOFF) 22 { 23 if (n < 3) 24 *lo = *hi = (n == 2); 25 else 26 *lo = *hi = FLINT_PRIME_PI_ODD_LOOKUP[(n-1)/2]; 27 } 28 else 29 { 30 /* 14/10 < 1/log(2)*/ 31 *lo = (n / (10 * FLINT_CLOG2(n))) * 14; 32 /* 19/10 > 1.25506/log(2) */ 33 *hi = (n / (10 * FLINT_FLOG2(n)) + 1) * 19; 34 } 35 } 36 37