Mathematics Magazine for Grades 1-12
Formulas for and the th Prime
Sebastian Martin Ruiz and Jonathan Sondow
1. THE FORMULAS: In ,  the first author gave a formula for the th prime number that involves only the elementary operations and the floor function. His conditional proof assumed certain inequalities based on the Prime Number Theorem. In this note, we use the inequalities of Rosser and Schoenfeld 
to give a complete proof of the slightly modified formula
(1) , >1,
where , defined as the number of primes not exceeding , is given by the formula
After the proof, we indicate various ways to modify and implement the formulas so that they operate in times and , respectively.
2. PROOF. For a positive integer, let
denote the number of divisors of . In , the first author found the formula
which holds since the quantity in parentheses is 1 or 0 according as does or does not divide .
Let F be the characteristic function of the set of prime numbers
From (3), we have if is prime, and >2 if is composite.
Since for >1, we have the formula
(6) , >1.
Using (5), we write the prime-counting function as the sum
with the convention that any sum is zero if . From (7), (6), (4), we obtain the formula (2) for .
In order to derive formula (1) for from (2), we require the following lemma.
Lemma 1. For >1, we have the inequalities
Proof: Rosser and Schoenfeld  proved that
(10) , all ,
(11) , .
From (10), we have . Since , it follows that
, which implies (8) if .
To prove (9) for , we verify it numerically for 2, 3, …, 20,
and note that (11) implies (9) for . This proves the lemma.
For , Lemma 1 implies that
The desired formula for the th prime number follows immediately. This completes the proof of (1) and (2).
3. IMPROVEMENTS. As they stand, the formulas for , and
operate in times , and , respectively. We can improve these bounds by modifying the formulas as follows. If divides , so does , so to compute it suffices to consider only . This reduce the times for
and to and ,respectively. For , compute (and thus ) for , then compute recursively as . This reduces the time for to .
We can also improve the computation times (but not the bounds) in the following two ways. First, instead of the floor of , use the integer quotient
of by . Second (as P. Sebah  has pointed out), in formulas (2) and (7) for
, after we only need to sum over odd numbers, after only over numbers relatively prime to 6, and similarly for other moduli 30, 210, 2310,….
This “sieving” cuts computation time by a factor of , where is the Euler’s totient function.
We thank P. Sebah for discussions on the bounds, C. Rivera for the square root optimization, and J. McCranie for the quotient acceleration.
1. J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers. Ill. J. Math. 6 (1962) 64-94.
2. S. M. Ruiz, A functional recurrence to obtain the prime numbers using the Smarandache Prime Function, Smarandache Notions Journal 11 (2000) 56.
3. S. M. Ruiz, The general term of the prime number sequence and the Smarandache Prime Function. Smarandache Notions Journal 11 (2000) 59.
4. S. M. Ruiz, Applications of Smarandache Functions and Prime and Coprime Functions, American Research Press, Rehoboth, 2002.
5. P. Sebah, private communications, October- November, 2002.
Avda. de Regla, 43 Chipiona 11550 Spain
209 West 97th St. New York, NY 10025