What is the fastest way of finding prime between $n$ and $2n$, considering $n<2^{32}$?

I'm talking about Bertrand's postulate.

  • 3
    $\begingroup$ Choosing a number from the interval randomly and testing its primality is better of an idea that you might think - for $n$ large the probability of hitting a prime is about $1/\log n$ by the prime number theorem. If you are careful to not pick numbers divisible by small primes, like $2,3,5$, then you already are improving by a factor of about $4$. $\endgroup$ – Wojowu Apr 21 '17 at 18:56
  • 1
    $\begingroup$ Here's a MathJax tutorial :) $\endgroup$ – Shaun Apr 21 '17 at 18:56
  • $\begingroup$ @DietrichBurde I have no idea.Stackoverflow lets other people edit my questions without asking me. $\endgroup$ – Murad Apr 21 '17 at 19:00
  • $\begingroup$ @Murad Although your question is related to primes, the name 'prime' is also given to ideals, rings, as well as other categories. That's why the 'prime-numbers' tag is better for attention. I also think that if you give more information like precomputational limits or method of calculation? $\endgroup$ – mdave16 Apr 21 '17 at 19:14
  • $\begingroup$ Brute force, if n is small :) $\endgroup$ – Prince M Apr 21 '17 at 19:28

What do you mean by "fastest way"? Do you need the answer for many different $n$, or just one? Are you allowed to precompute anything? If so, how much time and space are you allowed to use?

Since $2^{32}$ is only about 4 billion, if you need to find primes for many different queries $n$, you can easily pregenerate the full sorted list of primes up to $2^{32}$ using the Sieve of Eratosthenes (or download the list from the Internet).

Then for each query $n$, do a binary search on the list of primes to find one in the desired interval.

Thinking more about this, you can do even better, with precomputation. For instance since $2^{32}+15$ is prime, you can return it for any $n\geq 2^{16}+8$. Then $2^{16}+15$ is prime and you can return it for any $ 2^8+8 \leq n <2^{16}+8$, etc.

  • 1
    $\begingroup$ There are $203280221$ primes less than $2^{32}$. That's about a $25$Mb bit map. $\endgroup$ – lhf Apr 21 '17 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.