How to Find the Nth Prime Number in Batch Script

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

Why Check Up to the Square Root?

If a number n has a factor greater than sqrt(n), the corresponding co-factor must be less than sqrt(n) and would have already been found. Checking divisors only up to sqrt(n) instead of n/2 dramatically reduces the number of iterations. For example, testing candidate 541 checks divisors up to 23 instead of 270.

goto Inside for /L

Batch's for /L loop internally iterates through its full range even after a goto transfers control out of the loop body. The goto :sqrt_done exits the loop's code block immediately when the square exceeds the candidate, but the loop counter continues incrementing silently in the background until it reaches the end value. For the square root calculation of small candidates, this overhead is negligible. For very large candidates, this is an inherent limitation of Batch's for /L implementation.

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 Skip Even Numbers?

After 2, every even number is divisible by 2 and therefore not prime. By incrementing candidates by 2 (checking only odd numbers) and dividing only by odd divisors, the script eliminates half of all candidates and half of all trial divisions. This roughly quadruples the speed compared to the basic version.

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

Performance

Trial division is the slowest method for finding primes. Even with the square root optimization and even-number skipping, Batch's interpreted loop overhead makes this impractical for large values of N. Finding the 100th prime (541) completes in seconds, but the 1000th prime (7919) may take minutes. For large N values, use PowerShell or another compiled language.

32-Bit Limit

Batch's set /a arithmetic is limited to signed 32-bit integers (max 2,147,483,647). This is more than sufficient for this task, the 100,000th prime is only about 1.3 million, well within range. The practical limit is execution speed, not integer overflow.

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.