# The nth prime calculator

How to prove the correctness of the following algorithm :

Input: $$n$$ : the ordinal number

Output: $$x$$ : the nth prime number

$$b_1=6$$ , $$b_2=6$$ , $$b_3=6$$

If $$n==1$$ , then $$x=2$$ , else $$x=3$$

$$k=4$$ , $$m=3$$

While $$m \leq n$$ do:

$$\phantom{5}$$ $$b_4=b_1+ \operatorname{lcm}(k-2,b_1)$$

$$\phantom{5}$$ $$a=b_4/b_1-1$$

$$\phantom{5}$$ $$k=k+1$$

$$\phantom{5}$$ $$b_1=b_2$$ , $$b_2=b_3$$ , $$b_3=b_4$$

$$\phantom{5}$$ If $$x then $$x=a$$ , $$m=m+1$$

Return $$x$$

You can run this code here .

GUI application that implements this algorithm can be found here .

Fast command line program that implements this algorithm can be found here .

I can confirm that algorithm produces correct results for all $$n$$ up to $$10000$$ .

• $10000$ is a small number in this context. You should explain what your routine is doing, not just post the code. It will be easier to find what is wrong with a description of the algorithm – Ross Millikan May 31 '18 at 15:33
• Seems to be a very ineffective method. If I compute with 32-bit integers, it overflows for $n \ge 10$ (using $\mathrm{lcm}(a,b)=ab/\gcd(a,b)$). What is the purpose of the algorithm? – gammatester May 31 '18 at 15:41
• Not easy to determine what the algorithm does. It might be trial division. – Peter May 31 '18 at 15:46

## 2 Answers

Consider the variable $k$. Apart from the initialisation and increment, it is only used once, as $k-2$. It is therefore clearer if we simply lower its value by $2$ throughout:

b1 = 6 , b2 = 6 , b3 = 6
If n == 1, then x = 2 , else x = 3
k = 2, m = 3
While m ≤ n
do:
b4 = b1 + lcm(k, b1)
a = b4/b1 − 1
k = k + 1
b1 = b2 , b2 = b3 , b3 = b4
If x < a then x = a , m = m + 1
Return x


Next, let's substitute the expression for $b_4$ into the expression for $a$.

$$a=\frac{b_4}{b_1}−1 = \frac{b_1+\textrm{lcm}(k,b_1)}{b_1}-1 = \frac{\textrm{lcm}(k,b_1)}{b_1} = \frac{k}{\gcd(k,b_1)}$$

b1 = 6 , b2 = 6 , b3 = 6
If n == 1, then x = 2 , else x = 3
k = 2, m = 3
While m ≤ n
do:
b4 = b1 + lcm(k, b1)
a = k/gcd(k, b_1)
k = k + 1
b1 = b2 , b2 = b3 , b3 = b4
If x < a then x = a , m = m + 1
Return x


Basically what is happening is that $k$ is continually incremented. If it is a prime, then $\gcd(k,b_1)$ will be $1$, and $a$ will have the same value. The if statement will increment its prime counter, and store the prime in $x$. If the counter is at the requested value, the prime is returned.

If $k$ is not prime, then the $\gcd$ is highly likely not $1$ and $a$ is a smaller value than the previous prime found. The if statement will then do nothing, and the loop continues.

The only thing that remains to be shown is that $\gcd(k,b_1)$ is always larger than $1$ if $k$ is not prime. To be more precise:

Let $b_i$ be a sequence defined by $$b_1=b_2=b_3=6\\ b_{i+3}=b_i+\textrm{lcm}(i+1,b_i)$$

It remains to be shown that $\gcd(k,b_{k-1})>1$ for all composite $k$.

The $b_i$ are highly composite ($b_{i-3}|b_i$) and the sequence grows large very quickly. Furthermore it starts with sixes so that it has factors $2$ and $3$ to begin with. That could well be enough to make it work for the relatively small $n$ that it has been tested with. I wouldn't expect it to fail until you get to large semiprimes, i.e. large composite numbers without small factors.

• The cycle can be simplified: $a= k/\gcd(k, b1); b4 = b1(1+a)\cdots$ – Yuri Negometyanov Jun 7 '18 at 22:32

Updated 11.06.18

The proposed calculator enumerates the prime numbers on the pass.

Let us construct the similar algorithm based on the ideas of Eratosthenes sieve.

m = 1;
x = 2;
b = 2;
while (m < n)
{
for(k = 3; ; k = k+2)
{
if(gcd(b,k)==1)
{
x = k;
m = m + 1;
b = b * x;
}
}
}
return x;


In the both of the algorithms, a sequence of positive integers is tested for the presence of a common factor with a high composite number $b.$ If it equals to 1, then the integer is prime.

The algorithm above shows that it's sufficiently to use $b$ which equals the primorial $x\#$.

The OP calculator algorithm forms the greater value of $b,$ which contains any prime $p$ in the degree $d,$ wherein $$p^d\le x < p^{d+1},$$ but uses its delayed value.

This means that the OP calculator can be improved.

At this time, analysis of delaying influence shows that OP calculator is correct.