Skip to main content

How to Generate All Prime Numbers Up to N (Sieve of Eratosthenes) in Batch Script

The Sieve of Eratosthenes is one of the oldest and most efficient algorithms for finding all prime numbers up to a given limit N. It works by iteratively marking the multiples of each prime number as "Not Prime," starting from 2. After the sieve completes, all unmarked numbers are prime. While Batch is not optimized for heavy computation, this algorithm works well for small values of N (up to a few hundred).

In this guide, we will demonstrate how to implement the Sieve of Eratosthenes using environment variables as a "Boolean array."

The Strategy: Mark and Sweep​

  1. Create a variable for every number from 2 to N, initially marked as "Prime" (1).
  2. Start with the first prime (2).
  3. Mark all multiples of 2 as "Not Prime" (0).
  4. Move to the next unmarked number (3) and repeat.
  5. Continue until you've processed up to sqrt(N).
  6. All remaining marked numbers are prime.

Implementation Script​

@echo off
setlocal enabledelayedexpansion

set /p "limit=Find all primes up to: "

:: 1. Initialize all numbers as "Prime" (1)
for /L %%i in (2,1,%limit%) do set "IS_%%i=1"

:: 2. Calculate the square root boundary
:: We only need to sieve up to sqrt(limit)
set "sqrtLimit=1"
for /L %%i in (1,1,%limit%) do (
    set /a "sq=%%i * %%i"
    if !sq! LEQ %limit% set "sqrtLimit=%%i"
)

:: 3. The Sieve Loop (only up to sqrt of limit)
for /L %%i in (2,1,!sqrtLimit!) do (
    if !IS_%%i! EQU 1 (
        :: Mark all multiples of %%i as NOT prime, starting from %%i * %%i
        set /a "start=%%i * %%i"
        for /L %%j in (!start!,%%i,%limit%) do (
            set "IS_%%j=0"
        )
    )
)

:: 4. Collect and Display Results
set "primes="
set "count=0"
for /L %%i in (2,1,%limit%) do (
    if !IS_%%i! EQU 1 (
        set "primes=!primes! %%i"
        set /a "count+=1"
    )
)

echo.
echo ==========================================
echo PRIMES UP TO %limit% (!count! found^):
echo !primes!
echo ==========================================
pause
Why Start Marking at i * i?

When marking multiples of a prime i, all multiples smaller than i * i have already been marked by smaller primes. For example, when processing prime 5, the multiples 10 (2×5), 15 (3×5), and 20 (4×5) were already marked when processing 2 and 3. Starting at i * i = 25 avoids redundant work.

for /L Range Is Fixed at Parse Time

Batch evaluates the for /L start, step, and end values once when the statement is parsed. The inner loop for /L %%j in (!start!,%%i,%limit%) works because !start! is resolved via delayed expansion before the inner for /L begins executing. However, !start! cannot be changed mid-iteration, it is read once when the inner loop initializes.

Why Use the Sieve of Eratosthenes?​

  1. Efficiency: It is significantly faster than checking each number individually for primality.
  2. Bulk Generation: If you need a complete list of primes (e.g., for hashing, testing, or education), the sieve generates them all in one pass.
  3. Algorithmic Elegance: It is a classic "elimination" algorithm that demonstrates the power of marking and sweeping through data.

Important Limitations​

Performance and Memory

Each number from 2 to N requires a separate environment variable. For N = 1000, that is 999 variables, manageable. For N = 10000, the script becomes very slow due to Batch's loop overhead. Expect this script to take several seconds for N > 500 and potentially minutes for N > 2000. Batch is best suited for sieving values up to a few hundred.

Output Length

For large values of $N$, the concatenated primes string can exceed the maximum environment variable length (8191 characters). If you only need to display the primes, echo each one individually inside the collection loop instead of building a single string.

Conclusion​

Implementing the Sieve of Eratosthenes in Batch is a powerful demonstration of algorithmic thinking within a constrained environment. By using the "Mark and Sweep" methodology, you generate a complete list of primes with elegant efficiency. This technique strengthens your understanding of nested loops, boolean arrays, and elimination algorithms, skills that are directly transferable to building advanced data-filtering and analysis tools.

Table of Contents