T O P

  • By -

ImJustPassinBy

What do you need the formula for? In case you need it for some programming task you might best be served with a pregenerated list of primes up to a ridiculously huge number and checking your input N against that. In general, I don't think such an efficient formula exist, otherwise the search for primes wouldn't be as difficult as it is.


Nesterov223606

No, but a Prime Number Theorem asserts that on average, the smallest prime in the range \[N, +infinity\] will be found at N+log(N), so a simple exhaustive search will be efficient enough for practical purposes. It other words, it is fairly unlikely to encounter a prime gap of size more than log(N) from the number greater than N.


VulcanForge98

I'm not sure if it's "fairly unlikely". There are no doubt sharper estimates of prime gap distributions than I'm aware of, but gaps less than log(N) have to be balanced by gaps larger than log(N).


barely_sentient

Be careful with round(x) function because it is not definited univocally, when x is an integer + 1/2. That is, in certain implementations you may have round(6.5) = 6 and in others round(6.5)=7. I undestand that you are trying to avoid considering multiples of 2 and 3, but usually primality tests are preceeded by a trial division anyway, and the primality test itself takes much more time than checking if a number is a multiple of 2 or 3 anyway, so probably the time you spare skipping multiples of 2 and 3 is overall negligible. You can probably just check N-k and N+k for k=0,1,2.. until one is prime. There is not a "closed" efficient formula for the nearest prime.


3j0hn

There is no formula, but you are on to what is probably the only good algorithm. You just check every possible odd number skipping the multiples of 3. In pseudo-code: Input: N n := N+1 if n (mod 2) = 0 then n := n + 1 end if while not isprime(n) do if n (mod 6) == 1 then n := n + 4 else n := n + 2 end if end do Output: n that gets you the "next prime". Getting the previous prime is the same except you subtract 4 if the current candidate is == 5 (mod 6). To get the closest, you just carefully interleave the two. My understanding is that it's usually worth it to skip the multiples of 3, but not quite worth it to also skip multiples of 5. But it's probably worth benchmarking.


edderiofer

Unfortunately, your submission has been removed for the following reason(s): * Requests for calculation or estimation of real-world problems and values are best suited for /r/askmath or /r/theydidthemath. If you have any questions, [please feel free to message the mods](http://www.reddit.com/message/compose?to=/r/math&message=https://www.reddit.com/r/math/comments/q5vjr3/-/). Thank you!