A few days ago I posted a basic implementation of the Sieve of Eratosthenes.

The Sieve is great for finding all the numbers under n that are prime. For example, what are all the prime numbers under 1,000,000?

But what about if I want to find the nth prime? For example, what is the 10,001st prime number?

Since we need to pass the Sieve algorithm an “upper bound” number to use when creating the prime collection, it stands to reason that if we could somehow make an educated guess about the neighborhood of the nth prime number, then we could create a Sieve using that guess as the upper bound and extract our target prime from the resulting list.

Turns out the Prime number theorem can be used for this purpose. The details are way over my head, but there is a formula based on this theorem which can help in approximating the nth prime:

Approximations for the nth prime number

The first, more basic expression states that the nth prime is approximately n * log(n)

I struggled with this expression for a bit, as I thought the base of the log was the “natural” log. Turns out that the formula actually works when the base is 2. (if you can help to explain this please contact me)

So here’s a way to use the Sieve method from the other day to extract the nth prime number.

import scala.collection.mutable.ArrayBuffer

class PrimeCalculator {
  def primesUnder(n: Int): List[Int] = {
    if (n <= 1) List()
    else {
      val A = ArrayBuffer.fill(n + 1)(true)
      for (i <- 2 to Math.sqrt(n).toInt if A(i)) {
        for (j <- (i * i) to n by i) {
          A.update(j, false)
        }
      }

      (for (m <- A.indices if A(m)) yield m)
        .drop(2)
        .takeWhile(_ < n)  
        .toList
    }
  }

  def nthPrime(n: Int): Int = {
    // Math.log() uses the natural log base, dividing by Math.log(2) gives us the base 2 result
    val upperBound = (n * Math.log(n) / Math.log(2)).toInt
    // remember our list is 0 indexed...
    primesUnder(upperBound)(n-1)
  }
}

Test Suite:

import org.scalatest.{FlatSpec, Matchers}

class PrimeCalculatorTest extends FlatSpec with Matchers {

  it should "return the nth prime number" in {
    val primeCalculator = new PrimeCalculator
    primeCalculator.nthPrime(10) should equal(29)
    primeCalculator.nthPrime(10001) should equal(104743)
    primeCalculator.nthPrime(1000000) should equal(15485863)
  }
}