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)19 void 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