During a programming contest I was asked to find just smallest prime number to given number N. As Sieve cannot be used and brute force also doesn't work.
So, I was wondering is there any other faster implementation.
Here N -> (2, 10^18).
During a programming contest I was asked to find just smallest prime number to given number N. As Sieve cannot be used and brute force also doesn't work.
So, I was wondering is there any other faster implementation.
Here N -> (2, 10^18).
By fast primary testing you can test whether a given number is probably prime or not, actually methods like Miller Rabin are very fast and because we know the gap of size $O(\log n)$, between two consecutive primes, you can expect that when you start from $N$, you should visit few numbers by fast primarily testing, also, in most cases, fast primarily testing algorithms for the range you mentioned are correct.
In your case, because your numbers are bounded just few composite numbers can pass the miller rabin test which are:
2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321
You can see them in this list, So you just need to check the number that passed the Miller Rabin test, is in above list or not, and by using this code, is possible to do it in less than a second.
Use a sieve first before running the probabilistic primality testing algorithm. Make a list of the first $L$ primes (you'll have to decide on $L$, which should depend on $N$), and compute $N \pmod {p_i}$ for each of these primes. Now create an array of size $C\log N$ covering the $C\log N$ numbers culminating in $N$ (you'll have to decide on the constant $C$), and using the values of $N \pmod{p_i}$, mark off all multiples of $p_i$. When you're done going over the first $L$ primes, you will have a substantially reduced collection of integers to test for primality.
As a simple illustration, if you just mark off even numbers, your algorithm will run twice as fast; also multiples of $3$, thrice as fast; in general, the speedup factor is $(1-1/p_1)\ldots(1-1/p_L) \approx 1/\log L$. Using this approximation, you should be able to estimate what value of $L$ you should choose (but be sure to try it out anyway).
If n ≤ $10^{18}$ then checking whether n is prime by doing trial division would be reasonably fast; you can use only divisors that are not divisible by 2, 3 and 5 (8 out of 30) or not divisible by 2, 3, 5 and 7 (48 out of 210), meaning about 230 million divisions.
You can implement a sieve for the numbers n - 500 to n at quite exactly the same speed. That lets you find the next smallest prime in maybe 3 or 4 seconds.
Finding the next smaller probable prime using the Miller-Rabin test should be significantly faster, but then it is probabilistic.