What is the fastest way to find the dash between n and 2n

The fastest way is probably to pre-compute and store a 1-dimensional array of size 2^32

where the value for the index n

is the desired prime between n

and 2n

. Surely that would be outrageous memory usage, but it is probably the fastest.

A slightly slower way to use much less memory is to pre-compute and store a list of all Bertrand primes, where the first element is the first prime, and each element after the first is the largest prime less than the previous double. You can use a binary search on this list to quickly find the prime you want. If you want 1 < n < 2^32

, you need the finishing touch on this list above 2^32

to catch all of these n

. This would require a list of 34 primes, very doable. By the way, if you want to do this before 2^64

, you only need 66 primes.

Here is Python 3.5 code to implement this algorithm. It uses the binary search feature in the standard library. Bertrand's list of primes was found using another simple Python routine, although it is also available in the Online Encyclopedia of Integer Sequences , sequence A006992.

from bisect import bisect_right

_bertrand_primes = [
             2,          3,          5,          7,         13,         23,
            43,         83,        163,        317,        631,       1259,
          2503,       5003,       9973,      19937,      39869,      79699,
        159389,     318751,     637499,    1274989,    2549951,    5099893,
      10199767,   20399531,   40799041,   81598067,  163196129,  326392249,
     652784471, 1305568919, 2611137817, 5222275627]

def prime_between_n_and_2n(n):
    """Find a prime number p such that n < p < 2n. The returned value
    will be the first 'Bertrand prime' <https://oeis.org/A006992>
    greater than n. n is limited to 1 < n < 2**32 but need not be an
    integer. Outside those limits, None is returned.
    """
    if 1 < n < 2**32:
        return _bertrand_primes[bisect_right(_bertrand_primes, n)]