Question

How to find the Nth prime number in JavaScript

Answer 1

/**
 * Estimates a safe upper bound for the N-th prime number using the
 * Prime Number Theorem: p_n ~ n * ln(n).
 *
 * @param {number} n - The target prime index (1-based)
 * @returns {number} An upper bound guaranteed to be greater than or equal to the N-th prime
 */
function estimateUpperBound(n) {
  if (n < 6) {
    // Hardcoded threshold for small N where n * ln(n) undercounts
    return 15;
  }
  // Formula: n * (ln(n) + ln(ln(n))) provides a proven strict upper bound for n >= 6
  const fn = n;
  const logN = Math.log(fn);
  const logLogN = Math.log(logN);
  
  return Math.ceil(fn * (logN + logLogN));
}

/**
 * Finds the N-th prime number (1-based index) using the Sieve of Eratosthenes.
 *
 * @param {number} n - The 1-based index of the prime number to find (e.g., 1 -> 2, 2 -> 3)
 * @returns {number} The N-th prime number
 * @throws {RangeError} If n is not a positive integer
 */
function getNthPrime(n) {
  if (!Number.isInteger(n) || n < 1) {
    throw new RangeError("Index 'n' must be a positive integer (>= 1).");
  }

  const limit = estimateUpperBound(n);

  // Array where index represents the integer, initialized to 1 (true).
  // Uint8Array is memory-efficient and offers fast typed array performance in modern JS engines.
  const isPrime = new Uint8Array(limit + 1);
  isPrime.fill(1, 2); // 0 and 1 are not prime; mark numbers >= 2 as potentially prime

  const sqrtLimit = Math.sqrt(limit);

  // Sieve of Eratosthenes algorithm
  for (let p = 2; p <= sqrtLimit; p++) {
    if (isPrime[p] === 1) {
      // Mark multiples starting from p^2, stepping by p
      for (let multiple = p * p; multiple <= limit; multiple += p) {
        isPrime[multiple] = 0;
      }
    }
  }

  // Count primes until reaching the N-th prime
  let count = 0;
  for (let i = 2; i <= limit; i++) {
    if (isPrime[i] === 1) {
      count++;
      if (count === n) {
        return i;
      }
    }
  }

  throw new Error(`Failed to find the ${n}-th prime within estimated upper bound.`);
}

/**
 * Test runner function to demonstrate functionality across multiple target indices.
 */
function runTests() {
  const testCases = Object.freeze([2, 5, 8, 123, 7834, 21000]);

  console.log("N-th Prime Calculations:\n" + "=".repeat(30));

  for (const n of testCases) {
    const startTime = performance.now();
    const prime = getNthPrime(n);
    const elapsedTime = (performance.now() - startTime).toFixed(2);

    console.log(`N = ${n.toString().padStart(5)} | Prime = ${prime.toString().padStart(8)} | Time = ${elapsedTime}ms`);
  }
}

runTests();



/*
run:

N-th Prime Calculations:
==============================
N =     2 | Prime =        3 | Time = 0.06ms
N =     5 | Prime =       11 | Time = 0.00ms
N =     8 | Prime =       19 | Time = 0.01ms
N =   123 | Prime =      677 | Time = 0.06ms
N =  7834 | Prime =    79979 | Time = 3.96ms
N = 21000 | Prime =   237203 | Time = 1.16ms

*/

 

70+ SQL courses for beginners and professionals