# 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}$?

• 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$. – Wojowu Apr 21 '17 at 18:56
• – Shaun Apr 21 '17 at 18:56
• @DietrichBurde I have no idea.Stackoverflow lets other people edit my questions without asking me. – Murad Apr 21 '17 at 19:00
• @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? – mdave16 Apr 21 '17 at 19:14
• Brute force, if n is small :) – 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.
• There are $203280221$ primes less than $2^{32}$. That's about a $25$Mb bit map. – lhf Apr 21 '17 at 19:16