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).
$\begingroup$
$\endgroup$
-
1$\begingroup$ Why do you say that a sieve cannot be used? $\endgroup$ – Yuval Filmus May 8 '13 at 13:32
-
$\begingroup$ @YuvalFilmus it is impossible to create a array of size 10^18 in c++ thats why... $\endgroup$ – user7711 May 8 '13 at 13:36
-
1$\begingroup$ So you're doing the sieve wrong. You only want to sieve over $O(\log N)$ integers. $\endgroup$ – Yuval Filmus May 8 '13 at 13:37
-
$\begingroup$ @YuvalFilmus can you provide some reference for the algorithm??? $\endgroup$ – user7711 May 8 '13 at 13:39
-
$\begingroup$ Have a look at my answer. The algorithm is pretty standard, used for example in the quadratic sieve (for a different purpose). $\endgroup$ – Yuval Filmus May 8 '13 at 13:40
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ the implementation you provided what does it returns. $\endgroup$ – user7711 May 8 '13 at 8:59
-
$\begingroup$ Saeed , still not working, for 10^18 it takes 1 min on my system :(. $\endgroup$ – user7711 May 8 '13 at 9:22
-
$\begingroup$ @user7711, the implementation I provided, is for long in C#, I don't know your specific language, but you should convert it to big int or something like this, then works, I'm pretty sure it works fast, because I personally use it in some competition and it was fast (not in the long format in biginteger format), so this is just an exercise to convert it to big integer, and if you are not going to do this. $\endgroup$ – user742 May 8 '13 at 10:06
-
$\begingroup$ I am using C++ and unsigned long long works perfectly for 10^18. I have applied the changes in the code you gave but still i am not getting the solution :( $\endgroup$ – user7711 May 8 '13 at 10:11
-
$\begingroup$ @user7711, If you have a problem with code you can talk about it in the main site or code review, you can say your requirements there (time limit, ...), also you can mention that you used the linked implementation. This site is for algorithm, and not for the implementation. I just mentioned implementation as a post script. Also I should say that with 99.99999999% probability you are wrong, you doing something wrong, your range is very easy for miller rabin. You can put your code on ideone.com, and discuss about it in code review. $\endgroup$ – user742 May 8 '13 at 11:11
$\begingroup$
$\endgroup$
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).
answered May 8 '13 at 13:32
-
$\begingroup$ In miller rabin if you know what are the pseudo prime numbers (respect to miller rabin test) you can skip them, and in this case we know there are less than 10 number with less than 18 digits which passes miller rabin. So miller rabin can be used directly very fast. $\endgroup$ – user742 May 8 '13 at 13:45
-
1$\begingroup$ Sieving might still make the process faster. If your algorithm is already fast enough for the range considered, you can try larger numbers for a meaningful comparison. $\endgroup$ – Yuval Filmus May 8 '13 at 13:50
-
$\begingroup$ I cannot understand how sieve is useful here? you do not need any iteration if you know forbidden primes, this is at most $O(\log^4 n)$ algorithm. P.S: I test it in IDEONE, for 4 numbers takes 0.1 second, so I think it's not a buttleneck at all. ideone.com/H84Bnu $\endgroup$ – user742 May 8 '13 at 13:59
$\begingroup$
$\endgroup$
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.
