Skip to content
Tutorial Reference

How to Find the Nth Prime Number in Batch Script

Learn how to find the Nth prime number using a Batch script with trial-division primality testing, including optimizations like skipping even numbers and checking divisors only up to the square root.

While the Sieve of Eratosthenes generates all primes up to a limit, sometimes you need a specific one, like "What is the 50th prime number?" Finding the Nth prime requires a different approach: you check each candidate number for primality one by one, counting each prime you find, until you reach the desired position.

In this guide, we will demonstrate how to find the Nth prime using a trial-division primality test.

The Strategy: Count Until You Get There

  1. Start with the first candidate: 2.
  2. Check if the candidate is prime (using trial division).
  3. If it is, increment your counter.
  4. When the counter reaches N, you've found your answer.

Implementation Script

@echo off
setlocal enabledelayedexpansion

set /p "target=Find which prime number? (e.g., 10 for the 10th prime): "

set "count=0"
set "candidate=1"

:next_candidate
set /a "candidate+=1"

:: Calculate square root of candidate for trial division limit
set "sqrtCand=1"
for /L %%s in (1,1,!candidate!) do (
    set /a "sq=%%s * %%s"
    if !sq! LEQ !candidate! set "sqrtCand=%%s"
    if !sq! GTR !candidate! goto :sqrt_done
)
:sqrt_done

:: Trial Division: Check if candidate is prime
set "isPrime=1"

for /L %%d in (2,1,!sqrtCand!) do (
    if !isPrime! EQU 1 (
        set /a "rem=candidate %% %%d"
        if !rem! EQU 0 set "isPrime=0"
    )
)

if !isPrime! EQU 1 (
    set /a "count+=1"
    if !count! EQU !target! (
        echo.
        echo ==========================================
        echo The prime number #!target! is: !candidate!
        echo ==========================================
        pause
        exit /b
    )
)

goto :next_candidate

Optimized Version: Skip Even Numbers

After confirming that 2 is prime, all even numbers can be skipped. This cuts the number of candidates in half:

@echo off
setlocal enabledelayedexpansion

set /p "target=Find which prime number? (e.g., 10 for the 10th prime): "

if !target! LSS 1 (
    echo [ERROR] Please enter a positive number.
    pause
    exit /b
)

:: Handle the first prime (2) as a special case
set "count=1"
if !target! EQU 1 (
    echo.
    echo The prime number #1 is: 2
    pause
    exit /b
)

:: Start checking odd candidates from 3
set "candidate=1"

:next_odd
set /a "candidate+=2"

:: Calculate square root of candidate
set "sqrtCand=1"
for /L %%s in (1,2,!candidate!) do (
    set /a "sq=%%s * %%s"
    if !sq! GTR !candidate! goto :sqrt_done2
    set "sqrtCand=%%s"
)
:sqrt_done2

:: Trial Division: Check only odd divisors
set "isPrime=1"

for /L %%d in (3,2,!sqrtCand!) do (
    if !isPrime! EQU 1 (
        set /a "rem=candidate %% %%d"
        if !rem! EQU 0 set "isPrime=0"
    )
)

if !isPrime! EQU 1 (
    set /a "count+=1"
    if !count! EQU !target! (
        echo.
        echo ==========================================
        echo The prime number #!target! is: !candidate!
        echo ==========================================
        pause
        exit /b
    )
)

goto :next_odd

Why Find the Nth Prime?

  1. Indexed Access: If your system uses the "Nth prime" as a seed for a pseudo-random function or a hash calculation, you need a way to retrieve it on demand.
  2. Mathematical Exploration: Answering questions like "How far apart are the 100th and 101st primes?" for educational tools.
  3. Testing: Using specific prime numbers to test hash table sizes, encryption parameters, or modular arithmetic logic.

Important Limitations

Conclusion

Finding the Nth prime number is a classic algorithmic challenge that combines primality testing with sequential counting. While Batch is not the fastest language for this task, implementing it demonstrates mastery of nested loops, modulo arithmetic, and conditional flow control. This skill set is directly applicable to building data validation tools, cryptographic helpers, and mathematical exploration scripts.

Navigation