2
$\begingroup$

So I was trying to find the time complexity of an algorithm to find the $N$th prime number (where $N$ could be any positive integer).

So is there any way to exactly determine how far $(N+1)$th prime number will be if $N$th prime number is already known ?

$\endgroup$
  • 6
    $\begingroup$ Of course there is a way – just check numbers going up from the $n$th prime until you find the next prime. But you probably want to know whether there is a more efficient method, or maybe you even want to know the best method. It seems that knowing the $n$ prime helps very little in finding the next one. E.g., if you want to know the first prime after $10^{1000}$, and I tell you the last prime before $10^{1000}$, that doesn't give you very much help at all. $\endgroup$ – Gerry Myerson Jan 6 '19 at 23:11
0
$\begingroup$

It depends on what you call large, and what theory you use. Using the fact all primes greater than 3 are 1 or -1 mod 6 and a Sieve of Sundaram style argument, you can show that any natural number n, of certain forms will create at most 1 half ( one prime one composite) of a twin prime pair. Specifically, the following make at least one of 6n+1 or 6n-1 composite: $$\begin{cases}6n+1,\quad\text{n=(6j+1)k+j or n=(6j-1)k-j}\\6n-1,\quad\text{n=(6j+1)k-j}\end{cases}$$ Where, k,j>0, in the case of semiprimes with roughly same size factors, j,k will be close together making each roughly $\frac{1}{6}\sqrt p$ p being the number you are trying to factor. Of course, the twin prime conjecture, says there's no point after which, all natural numbers are of these forms. Good luck.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

You're got what looks like two questions.

  1. The time complexity of the nth prime. In practice it is $O\big(\frac{n^{2/3}}{\log^2n}\big)$ using fast prime count algorithms. In theory this could be lowered to something on the order of $O(n^{1/2})$. See:

  2. Does knowing P(n-1) allow one to quickly find P(n)? Yes, in the sense that we have reduced the problem to a single nextprime call. Once beyond trivial sizes, this is just a loop calling isprime. One might want to use a wheel or a partial sieve to skip obvious composites.

    See Cramér's conjecture for a thought on how long this would take. In practice this is quite efficient, with inputs of thousands of digits being straightforward to calculate. You can look up the concept of "merits" for gaps. On average you'll find the next prime about $\log n$ away. For large inputs, I found sieving to a distance of $30 \log n$ (30 merits) was plenty to get excellent performance with exceptionally few gaps that need to look farther.

    Knowing the previous prime hasn't really given us any special information though, as Gerry pointed out.

| cite | improve this answer | |
$\endgroup$
-2
$\begingroup$

A good method for the operation of a prime number program is to output only the primes between an upper-bound and the upper-bound - k . Then the program just appears to be jumping from one section of a list to the other on each computation. Of course required consecutive primes are obviously found within the range of the output.

Here is my previous post:

Odd numbers can be wheeled in multiplications to output only odd composite numbers. Then the odd numbers that are not output are the prime numbers.

Now each inner loop can stop at a multiplication that reaches the value of an upper-bound and the outer loop can stop at the square root of the upper-bound.

Furthermore the loops from the number 11 can increment with 2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10 ... as continuing and repeating. That's a big performance gain because multiples of 3, 5, and 7 are removed from the sequence of odd numbers.

A prime number application really works best when outputting prime numbers between an upper bound and the upper bound - k. Then the application appears to be just scrolling sections (or jumping to sections) of a list on each computation. And in this case the loop increments are really only needed on the outer loop because a single division operation jumps over unneeded sections of the inner loop. Of course, array subscript locations can work with translations such that the same array can handle any of the segmented computations and then not use very much memory.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ My only comment is: "Huh?" $\endgroup$ – Matt Samuel Jan 6 '19 at 23:41
  • $\begingroup$ Description of a computational computer program is an algorithm. $\endgroup$ – S Spring Jan 7 '19 at 0:25
  • $\begingroup$ I don’t understand any of this, but it sounds like exhaustive search which doesn’t help OP. Whatever it is, it’s not an answer. $\endgroup$ – Randall Jan 7 '19 at 0:28
  • $\begingroup$ The OP doesn't need the primes to be counted but only needs the next prime after a counted prime. The algorithm does work in the situation. But odd composite numbers are output to an array and odd positions in the array that don't receive an output represent the prime numbers. Sections of prime numbers less than the upper-bound - k are jumped over in the computation. $\endgroup$ – S Spring Jan 7 '19 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.