1

i want to know if there is a easy way to find the prime number next to X.

For example, if X=2, the next prime will be 3. The algorithm that i have would be ok, if i wanted to know little numbers but i want to calculate like X=3 million.

I found a algorithm to calculate primes, but it takes a lot of time to calculate them, since it calculates all primes from 0 to X... For example for 1 million, it takes almost 2 minutes.

Question is... How can i find the next prime number? Is there an efficient algorithm? Best solution i found is to check if X+1 is prime and increase until one is found...

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
Pedro Lino
  • 601
  • 1
  • 9
  • 18
  • 4
    As 2 is the only even prime number you may use X+2 (if X itself is not 2). Also see [here](http://stackoverflow.com/questions/4475996/given-prime-number-n-compute-the-next-prime) – sb9 Mar 11 '15 at 12:57
  • See [this](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) – Robbie Dee Mar 11 '15 at 14:00
  • That takes a lot of time @RobbieDee . That was the one i was talking about i had. To do more work than N, i better do N/2 work then... – Pedro Lino Mar 11 '15 at 14:10
  • No - there are bounds for prime gaps however - and obviously you want to advance by `(+2)` for odd values. [Here](http://arxiv.org/pdf/1412.5029v1.pdf) are the incredibly gory latest details. In practical terms - advance by `(+2) (odd)` and test each candidate with a true test for primality, or a probabilistic (MR / Lucas / etc) test. – Brett Hale Mar 11 '15 at 14:13
  • Anecdotally, the algorithm should be good for values where N <= 10,000,000 but with the usual caveat of CPU speed/number of cores/memory, disk speed etc etc. I must confess I've never taken it beyond a million. What language are you using? – Robbie Dee Mar 11 '15 at 15:50

3 Answers3

3

What you need is to test for primality each number beginning at X. You can find such tests implemented in the GMP library or you can look at the snippet for Miller-Rabin algorithm in Rosetta code.

logc
  • 3,813
  • 1
  • 18
  • 29
  • This is helpful. It doesn't help much to avoid testing even numbers, since checking for small prime factors is normally the first step, so it hardly takes any time to recognize and reject numbers divisible by 2, or 19. If X is large enough (say, thousands or millions of digits), you might do slightly better by sieving out candidates divisible by small to moderate primes. – Douglas Zare Mar 11 '15 at 15:52
0

One possible solution is instead of increasing the number by one, you can increment the number by two if the number is odd else increment by one and then in all future iterations increment by two.

Like in the below code snippet

if (num is odd)
    check_prime_of(num+2);
else /*num is even and not equal to 2*/
    check_prime_of(num+1);
Santosh A
  • 5,173
  • 27
  • 37
  • You can further reduce the load by observing that after 2 and 3, all prime numbers are of the form 6*N+/-1 where N is an integer. You can also reduce the workload by keeping a table of known primes up to some limit, and the larger the table, the smaller the cost of computation. – Jonathan Leffler Mar 11 '15 at 13:58
  • This doesn't halve complexity. O(n) = O(n/2). – mafso Mar 11 '15 at 14:36
  • @JonathanLeffler: Yeah I agree with you. – Santosh A Mar 11 '15 at 15:05
  • @mafso : Yes the time complexity is not O(n), what I meant was the number of computation required in the later case is halved when compared to using the X+1 algorithm. – Santosh A Mar 11 '15 at 15:06
  • The amount of time is not halved because the time it takes to recognize a composite is not constant, and it takes almost no time to recognize that an even number is composite. It takes much longer to recognize that a product of two large primes is composite (although it is much faster to recognize this than to find the primes). – Douglas Zare Mar 11 '15 at 15:44
  • Good, but could be better. Over a given value all primes end in 1, 3, 7 or 9. *Usually* a jump of 2 but 3-->7 yields a duff iteration. – Robbie Dee Mar 11 '15 at 16:45
  • @Robbie Dee: That avoids divisibility by 2 and 5. However, it is standard in efficient primality checks to start by checking divisibility by many more small primes, so rejecting numbers divisible by 2 or 5 does not take a significant amount of time. This means there is little or no benefit to skipping testing numbers divisible by small primes. – Douglas Zare Mar 11 '15 at 17:50
  • I wasn't endorsing the algorithm - merely suggesting an improvement. – Robbie Dee Mar 11 '15 at 18:16
  • @RobbieDee - how do you know what the final *decimal* digit of a number is without conversion? (Think hundreds or even thousands of digits) And why stop there? You could convert to base-6 and eliminate all numbers that end in `3`. Or base-14 and numbers ending in `7`. – Brett Hale Mar 13 '15 at 06:18
0

I can double the speed of "if x+1 is prime" ..... For all x > 2, then x+1 will never be prime, so test x+2 instead :)

Other than that, no. There is no efficient algorithm to find the next prime after X. The "long time to calculate" is what makes public key cryptography (the basis of much of security on the Internet) possible. Public key is based on the difficulty of finding the two prime factors of a given large number; if finding the next prime after X was easy, then you could simply start at the square root of the large number and start counting up.

racraman
  • 4,988
  • 1
  • 16
  • 16
  • Yes, won't be finding many primes incrementing by 2 if x was even ! :). I was thinking of an algorithm that had just found a prime "x". – racraman Mar 11 '15 at 13:13
  • Your connection to the difficulty of factoring is not correct. If you had a constant time oracle who gave you the next prime, this would not let you factor numbers much faster. Trial division by primes is not much faster than trial division, which is quite far from the best factoring algorithms. – Douglas Zare Mar 11 '15 at 13:16
  • AFAIK, we haven't proven that such an algorithm cannot exist, though. –  Nov 18 '21 at 19:03
  • @MontanaBurr True - and since The Riemann Hypothesis is closely related to primes, so if that were proven it might lead to such an algorithm. Should such an algorithm be found, that would cause a lot of worry in internet security, but to date there is no sign of such an algorithm appearing (nor off the Riemann Hypothesis being proven or disproven) – racraman Nov 18 '21 at 22:38