Prime-Generating Formula

When dividing any positive integer $n$ by a positive integer $d$, the result will be an integer if and only if $d$ is a divisor of $n$. If $n$ is a prime number, its only divisors are $1$ and $n$ itself. To determine whether a number $n$ is prime, it suffices to check whether the division results in an integer for divisors $d$ from $2$ up to the greatest integer less than or equal to the square root of $n$. For prime $n$, none of the divisions by $k \in [2,\lfloor \sqrt{n} \rfloor]$ yields an integer. If we multiply the fractional parts of all these divisions, the result will be zero only when at least one of the factors is zero, that is, when the number is composite. Therefore, the function below, for $n > 3$, is zero only for composite numbers, and $1$ otherwise:

$$P(n)=\left\lceil\prod_{k=2}^{\lfloor \sqrt{n}\rfloor}\left(\frac{n}{k}-\left\lfloor\frac{n}{k}\right\rfloor\right)\right\rceil$$

For $n$ from $1$ to $3$, the empty product is equal to $1$. Since $1$ is not prime, we can multiply the value by

$$z(n)=\left\lceil\frac{n-P(n)}{n}\right\rceil$$

which is zero only for $n=1$. Thus, the function below, defined for positive integers, returns $1$ for any prime $n$, and $0$ otherwise:

$$f(n)=z(n) \cdot P(n)$$

The function $\pi(n)$ counts how many prime numbers exist from $1$ to $n$, using the function $f$ defined above:

$$\pi(n)=\sum_{m=1}^{n} f(m)$$

The value of $\pi(0)$ is defined as zero, corresponding to the empty sum.

Let us define a function $d_m(k)$ that equals $1$ when $k=m$, and $0$ otherwise:

$$d_m(k)=\left\lfloor \frac{1}{1+(m-k)^2} \right\rfloor$$

When $k \neq m$, the denominator is greater than $1$, and the entire expression evaluates to zero. Otherwise, it equals $1$. Thus, $d_n(k)$ equals $1$ only when $k=n$, for a fixed $n$.

If we have an upper bound $N$ for the $n$-th prime, we can construct a function that returns the $n$-th prime by summing the candidates $k$ that may be the $n$-th prime, multiplied by a function that selects only the first $k$ such that $\pi(k)=n$.

$$p(n)=\sum_{k=1}^{N} k \cdot d_n(\pi(k)) \cdot d_{n-1}(\pi(k-1))$$

When the index $k$ satisfies $\pi(k)=n$ and $\pi(k-1)=n-1$, we have found exactly the $n$-th prime.

Since $p(n)$ grows approximately as $n \ln n$, we can use upper bounds such as:

$$\begin{array}{l} N = \left\lfloor 2+n \cdot (\ln n + \ln \left( 1 + \ln n \right)) \right\rfloor \\ N = n^2+1 \\ N = 2^{2^n} \end{array}$$

The first is based on the fact that $p(n)$ is less than $n \cdot (\ln n + \ln(\ln n))$ for $n \geq 6$, with smaller cases verifiable directly. The last grows very rapidly and serves as a guarantee when one does not have a good estimate of the value of the prime $p(n)$.

Obviously, the formula is not efficient. It is merely a mathematical notation for the primality testing algorithm that uses successive divisions up to the square root of the number being tested.

This formula was created (discovered?) on 2026-05-04 by José Eduardo Gaboardi de Carvalho (edu.a1978 at gmail).