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...

Improve this question
5
  • 4
    As 2 is the only even prime number you may use X+2 (if X itself is not 2). Also see here Commented Mar 11, 2015 at 12:57
  • See this Commented Mar 11, 2015 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... Commented Mar 11, 2015 at 14:10
  • No - there are bounds for prime gaps however - and obviously you want to advance by (+2) for odd values. Here 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. Commented Mar 11, 2015 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? Commented Mar 11, 2015 at 15:50

4 Answers 4

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

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.
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);
Improve this answer

9 Comments

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.
This doesn't halve complexity. O(n) = O(n/2).
@JonathanLeffler: Yeah I agree with you.
@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.
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).
|
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.

Improve this answer

4 Comments

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".
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.
AFAIK, we haven't proven that such an algorithm cannot exist, though.
@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)
0 
-5 + 6 = 1   -1 × -1
1 + 6 = 7
7 + 6 = 13
13 + 6 = 19
19 + 6 = 25  5 × 5
25 + 6 = 31
31 + 6 = 37
37 + 6 = 43
43 + 6 = 49  7 × 7
49 + 6 = 55  5 × 11


 These square values are always prime 
 just like the next Composite is always 
 +6 more than the last multiple of 5, 
 7, 11, 17, 19, 23, 27, 29 etc


 -1 + 6 = 5
 5 + 6 = 11
 11 + 6 = 17
 17 + 6 = 23
 23 + 6 = 29
 29 + 6 = 35    5 × 7
 35 + 6 = 41
 41 + 6 = 47
 47 + 6 = 53
 53 + 6 = 59
 59 + 6 = 65    5 × 13 
 65 + 6 = 71
 71 + 6 = 77    7 × 11


 +30 for the fives
 +42 for the sevens

 6 times the next √ once the next prime 
 Root Pops up on the list ... some will 
 be higher powers but still prime 
 numbers
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.