How to find n+1 th prime number in minimum time?

Question

Mathematics

Is there (and if so, what) an algorithm that, given a list of n prime numbers from p_0 = 2 to p_n-1, would give p_n as not too long? In other words, is there an algorithm to find the next prime number ?

Answer 1

Yes - iterate over the next number, starting with p_(n-1)+1, then check the divisibility by all prime numbers as long as they are less than the root and the current number.
You can apply the following optimizations - start with p_(n+1)+2 and go with step 2 (only odd numbers). Iterate over numbers only of the form 6k-1 and 6k+1 (k is originally floor(p_(n-1)+3) / 6). Instead of calculating the root, the code should be squaring - something like while (i < n && p[i]*p[i] <= x) ... i++;.
This is if you are already given a list of previous primes. If you are thinking about an algorithm step that finds the first n primes or all primes up to some K, then it will be faster to use the sieve of eratosthenes .