CODEWITHSUNDEEP
algorithmmath
Bruno Snickers
Bruno Snickers

Reputation: 198

What is the fastest way of finding prime between n and 2n

What is the fastest way of finding prime between n and 2n,considering n<2^32.I'm talking about Bertrand's postulate

Upvotes: 3

Views: 402

Answers (1)

Rory Daulton
Rory Daulton

Reputation: 22534

The fastest way would probably to pre-compute and store a 1-dimensional array of size 2^32, where the value for index n is the desired prime number between n and 2n. This would be an outrageous use of memory, of course, but it probably is fastest.

A slightly slower way that uses much less memory is to pre-compute and store a list of all "Bertrand primes", where the first element is the first prime number and each element after the first is the greatest prime number less than double the previous element. You can use a binary search of that list to quickly find the desired prime number. If you want 1 < n < 2^32 you need the last prime in that list to be above 2^32 to catch all such n. That would need a list of just 34 prime numbers, very doable. By the way, if you want to do this up to 2^64 you need only 66 prime numbers.

Here is Python 3.5 code to implement that algorithm. It uses a binary search function in the standard library. The list of Bertrand primes was found with another simple Python routine, though 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)]

Upvotes: 2

Related Questions