Skip to content
Tutorial Reference

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

Learn how to implement the Sieve of Eratosthenes algorithm in Windows Batch to efficiently find all prime numbers up to a given limit N.

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 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

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.

Navigation