What is the fastest way of finding prime between $n$ and $2n$, considering $n<2^{32}$?
I'm talking about Bertrand's postulate.
$\begingroup$
$\endgroup$
5
-
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$– WojowuCommented Apr 21, 2017 at 18:56
-
1$\begingroup$ Here's a MathJax tutorial :) $\endgroup$– ShaunCommented Apr 21, 2017 at 18:56
-
$\begingroup$ @DietrichBurde I have no idea.Stackoverflow lets other people edit my questions without asking me. $\endgroup$– MuradCommented Apr 21, 2017 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$– mdave16Commented Apr 21, 2017 at 19:14
-
$\begingroup$ Brute force, if n is small :) $\endgroup$– Prince MCommented Apr 21, 2017 at 19:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Apr 21, 2017 at 19:08
-
1$\begingroup$ There are $203280221$ primes less than $2^{32}$. That's about a $25$Mb bit map. $\endgroup$– lhfCommented Apr 21, 2017 at 19:16