/**
* Estimates a safe upper bound for the N-th prime number using the
* Prime Number Theorem: p_n ~ n * ln(n).
*
* @param n - The target prime index (1-based)
* @returns An upper bound guaranteed to be greater than or equal to the N-th prime
*/
function estimateUpperBound(n: number): number {
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: number = n;
const logN: number = Math.log(fn);
const logLogN: number = Math.log(logN);
return Math.ceil(fn * (logN + logLogN));
}
/**
* Finds the N-th prime number (1-based index) using the Sieve of Eratosthenes.
*
* @param n - The 1-based index of the prime number to find (e.g., 1 -> 2, 2 -> 3)
* @returns The N-th prime number
* @throws {RangeError} If n is not a positive integer
*/
function getNthPrime(n: number): number {
if (!Number.isInteger(n) || n < 1) {
throw new RangeError("Index 'n' must be a positive integer (>= 1).");
}
const limit: number = estimateUpperBound(n);
// Boolean array where index represents the integer, initialized to true.
// Using Uint8Array is memory-efficient and offers fast typed array operations.
const isPrime: Uint8Array = new Uint8Array(limit + 1);
isPrime.fill(1, 2); // 0 and 1 are not prime; mark numbers >= 2 as potentially prime
const sqrtLimit: number = Math.sqrt(limit);
// Sieve of Eratosthenes algorithm
for (let p: number = 2; p <= sqrtLimit; p++) {
if (isPrime[p] === 1) {
// Mark multiples starting from p^2, stepping by p
for (let multiple: number = p * p; multiple <= limit; multiple += p) {
isPrime[multiple] = 0;
}
}
}
// Count primes until reaching the N-th prime
let count: number = 0;
for (let i: number = 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(): void {
const testCases: readonly number[] = [2, 5, 8, 123, 7834, 21000];
console.log("N-th Prime Calculations:\n" + "=".repeat(30));
for (const n of testCases) {
const startTime: number = performance.now();
const prime: number = getNthPrime(n);
const elapsedTime: string = (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.05ms
N = 7834 | Prime = 79979 | Time = 2.78ms
N = 21000 | Prime = 237203 | Time = 1.13ms
*/