Sieve of Eratosthenes: Basic Methods for Finding Prime Numbers with C++

🇬🇧 What is the Sieve of Eratosthenes and how does it work? In this article, we learn to find prime numbers step-by-step with C++ implementations using simple, odd, wheel, and segmented sieve methods.

Posted Aug 23, 2025

By fr0stb1rd

views 23 min read

Sieve of Eratosthenes: Basic Methods for Finding Prime Numbers with C++

Prime numbers are the building blocks of all whole numbers. They are fascinating for both their simplicity and the unpredictable nature of their distribution. Finding prime numbers, especially large ones, has been a fundamental problem in mathematics for centuries. One of the oldest and most elegant solutions to this problem is the Sieve of Eratosthenes, which has stood the test of time.

This method is named after the Greek mathematician Eratosthenes of Cyrene (276-195 BC) and is not based on testing each number individually to see if it is prime. Instead, it is built on systematically eliminating all non-prime numbers.

⚙️ How It Works

Let’s say you want to find the prime numbers up to 30:

First, write down all the numbers from 2 to 30 in a list:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Now, look at the list. The first number, 2, is our first prime. Let’s cross out the multiples of 2 (4, 6, 8, …, 30).

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
The next uncrossed number is 3. It’s also a prime! Now we eliminate the multiples of 3 (9, 12, 15, 18, …, 30).

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Our next prime is 5. But notice: it’s enough to start eliminating multiples of 5 from 25 (5²). This is because the multiples smaller than 25 have already been eliminated by 2 or 3.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
The next number is 7, but 7² = 49, which is greater than our limit of 30. So we can stop now.

The remaining numbers are the primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

💪 Why Is It So Powerful?

The beauty of the Sieve of Eratosthenes is that it doesn’t use division to check if a number is prime. It works only with addition and marking. This makes it an incredibly fast method for computers.

But it doesn’t end there. Today, different improved versions are used for larger ranges:

Segmented Sieve: Let’s say you want to find primes from 1 billion to 1 billion and 1000. It’s not possible to fit all numbers up to 1 billion in memory. This is where the segmented sieve comes in: it divides the range into small pieces (segments) and sieves each piece in turn. This greatly reduces memory usage.
Wheel Sieve: In cases where we know that some non-prime numbers will be eliminated automatically (for example, all even numbers), the elimination process is sped up.
Parallel and GPU-assisted sieves: There are methods that use many cores or a GPU simultaneously to calculate prime numbers on modern hardware.

🧮 Simple Sieve - The Basic Sieve of Eratosthenes

        
      
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> sieve_simple(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (is_prime[p]) {
            for (int i = p * p; i <= n; i += p)
                is_prime[i] = false;
        }
    }
    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) primes.push_back(i);
    return primes;
}

int main() {
    int n = 30;
    auto primes = sieve_simple(n);
    for (int p : primes) cout << p << " ";
    cout << "\n";
}

📦 Including Header Files

<vector> -> Dynamic array (vector) structure. We use it here to store prime numbers.
<cmath> -> Mathematical operations, especially for square root (sqrt).

🛠️ sieve_simple

        
      
vector<int> sieve_simple(int n)

n -> The upper limit for the prime numbers we want to find.
The function returns a vector<int>; that is, it gives the list of prime numbers as a vector.

🏷️ Primality marking array

        
vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;

is_prime[i] -> Stores whether the number i is prime.
Initially, all numbers are considered prime (true).
Since 0 and 1 are not prime, they are marked as false.

🔄 Prime number elimination loop

        
      
for (int p = 2; p * p <= n; p++) {
    if (is_prime[p]) {
        for (int i = p * p; i <= n; i += p)
            is_prime[i] = false;
    }
}

Outer loop: Starts from p = 2 and continues with the condition p * p <= n.
- It is sufficient to go up to √n. Because if a number has a small divisor, the large divisor would have already been marked in previous steps.
Inner loop: If p is prime, we mark all its multiples starting from p*p (p*p, p*(p+1), ...).
- i += p -> To step through the multiples.
- Marking as false -> this number is no longer prime.

📋 Collecting prime numbers

        
      
vector<int> primes;
for (int i = 2; i <= n; i++)
    if (is_prime[i]) primes.push_back(i);

After the marking is complete, all numbers with is_prime[i] == true are considered prime.
These numbers are added to the primes vector.

▶️ main

        
      
int main() {
    int n = 30;
    auto primes = sieve_simple(n);
    for (int p : primes) cout << p << " ";
    cout << "\n";
}

n = 30 -> We want to find prime numbers up to 30.
auto primes = sieve_simple(n); -> We call the function and get the result in the primes vector.
We print the prime numbers to the screen with a loop:
- for (int p : primes) -> Runs for each p in the vector.
- cout << p << " "; -> Prints the primes.

🧩 Algorithm

Mark 0 and 1 as not prime.
For numbers from 2 to √n:
- If the number is prime -> mark its multiples (not prime).
Unmarked numbers -> are prime.
Add all prime numbers to a list and print them.

Time Complexity: O(n log log n)
Memory Complexity: O(n)

💻 Let’s Run It

        
      
[fr0stb1rd@archlinux Desktop]$ mkdir demo && cd demo
[fr0stb1rd@archlinux demo]$ nano sieve_simple.cpp
[fr0stb1rd@archlinux demo]$ g++ -o sieve_simple sieve_simple.cpp -O2
[fr0stb1rd@archlinux demo]$ ./sieve_simple 
2 3 5 7 11 13 17 19 23 29 
[fr0stb1rd@archlinux demo]$ 

🥇 Sieve Optimized with Odd Numbers

        
      
#include <iostream>
#include <vector>

using namespace std;

vector<int> sieve_odd(int n) {
    if (n < 2) return {};
    int m = (n - 1) / 2;
    vector<bool> is_prime(m + 1, true);
    for (int i = 1; 2 * i + 1 <= n / (2 * i + 1); i++) {
        if (is_prime[i]) {
            int p = 2 * i + 1;
            for (int j = (p * p - 1) / 2; j <= m; j += p)
                is_prime[j] = false;
        }
    }
    vector<int> primes = {2};
    for (int i = 1; i <= m; i++)
        if (is_prime[i]) primes.push_back(2 * i + 1);
    return primes;
}

int main() {
    int n = 30;
    auto primes = sieve_odd(n);
    for (int p : primes) cout << p << " ";
    cout << "\n";
}

🧠 Logic of using odd numbers

vector<bool> is_prime(m + 1) -> now all numbers except 2 are represented by odd numbers.
This saves memory because even numbers cannot be prime and do not take up space in the vector.
🔢 Indexing and numbers

        
      
int m = (n - 1) / 2;

i -> index in the vector.
Number = 2*i + 1
Example: i=1 -> 3, i=2 -> 5, i=3 -> 7 …

🔁 Outer loop (√n optimization)

        
      
for (int i = 1; 2 * i + 1 <= n / (2 * i + 1); i++)

We only go up to 2*i + 1 <= √n.
Same optimization as the old version, but we are indexing for odd numbers.

✖️ Marking multiples

        
      
int p = 2 * i + 1;
for (int j = (p * p - 1) / 2; j <= m; j += p)
    is_prime[j] = false;

We start from p*p (other multiples are already marked in previous steps).
(p*p - 1)/2 -> the correct index in the vector.
j += p -> we only move between odd numbers.

✍️ Adding 2 manually

        
      
vector<int> primes = {2};

2 is not in the vector due to the odd number optimization -> it is added manually.

🏗️ Generating prime numbers

        
for (int i = 1; i <= m; i++)
    if (is_prime[i]) primes.push_back(2 * i + 1);

Every unmarked i -> the number 2*i + 1 is prime.
These numbers are added to the vector.

🧩 Algorithm

Memory is reduced by ~2× thanks to the odd number optimization.
The algorithm logic is exactly the same; the only difference is the indexing and marking strategy.
Provides performance improvement even in large ranges with small optimizations.

Time Complexity: O(n log log n) - same as the classic sieve, but the constant factor is smaller because only odd numbers are processed.
Memory Complexity: O(n/2) ≈ O(n) - about half the memory is saved because even numbers are not stored.

💻 Let’s Run It

        
      
[fr0stb1rd@archlinux demo]$ nano sieve_odd.cpp
[fr0stb1rd@archlinux demo]$ g++ sieve_odd.cpp -o sieve_odd -O2
[fr0stb1rd@archlinux demo]$ ./sieve_odd 
2 3 5 7 11 13 17 19 23 29 
[fr0stb1rd@archlinux demo]$ 

🛞 Wheel Sieve - 6k ± 1 Optimization

        
      
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> sieve_wheel(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 4; i <= n; i += 2) is_prime[i] = false;
    for (int i = 9; i <= n; i += 6) is_prime[i] = false;
    int limit = sqrt(n);
    for (int i = 5, step = 2; i <= limit; i += step, step = 6 - step) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i * 2)
                is_prime[j] = false;
        }
    }
    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) primes.push_back(i);
    return primes;
}

int main() {
    int n = 30;
    auto primes = sieve_wheel(n);
    for (int p : primes) cout << p << " ";
    cout << "\n";
}

💡 The idea of the wheel

The goal here is: to eliminate some sets of numbers (evens, multiples of 3) from the start, so there is less work to do in the outer loop.
The smallest wheel used is the 2 and 3 based wheel (wheel of 6).
- This means that potential prime candidates are only of the form 6k ± 1.

🚦 Initial elimination steps

        
for (int i = 4; i <= n; i += 2) is_prime[i] = false;  // evens are removed
for (int i = 9; i <= n; i += 6) is_prime[i] = false;  // some multiples of 3 are removed

First, all even numbers were eliminated.
Then, multiples of 3 like 9, 15, 21, ... were also eliminated (specifically those of the form 6k+3).

🔂 6-step progression in the loop

        
      
for (int i = 5, step = 2; i <= limit; i += step, step = 6 - step)

Thanks to this writing trick, i iterates through only 6k ± 1 numbers in order: 5, 7, 11, 13, 17, 19, ....
This way, numbers that cannot be prime are never checked.

✖️ Marking multiples

        
for (int j = i * i; j <= n; j += i * 2)
    is_prime[j] = false;

The reason for j += i*2 here is that since even numbers were removed at the beginning, we only look at odd multiples at each step. This reduces the workload by half.

📋 Collecting primes

        
for (int i = 2; i <= n; i++)
    if (is_prime[i]) primes.push_back(i);

After the elimination is finished, all remaining indices with a true value are added to the vector as primes.

🧩 Algorithm

Simple sieve -> checks all numbers.
Odd sieve -> checks only odd numbers.
Wheel sieve (mod 6) -> deals only with 6k ± 1 numbers.
With this method:
- Running time is reduced.
- Elimination is more organized.
- Performance gain is achieved, especially for large n values.

Time Complexity: O(n log log n) - same as the classic sieve but the constant factor is smaller because only 6k ± 1 candidates are tried.
Memory Complexity: O(n) - is_prime is kept for the entire 0..n range.

💻 Let’s Run It

        
      
[fr0stb1rd@archlinux demo]$ nano sieve_wheel.cpp
[fr0stb1rd@archlinux demo]$ g++ sieve_wheel.cpp -o sieve_wheel -O2
[fr0stb1rd@archlinux demo]$ ./sieve_wheel 
2 3 5 7 11 13 17 19 23 29 
[fr0stb1rd@archlinux demo]$ 

🧩 Segmented Sieve - For Large Ranges

        
      
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> simple_primes(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (is_prime[p]) {
            for (int i = p * p; i <= n; i += p)
                is_prime[i] = false;
        }
    }
    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) primes.push_back(i);
    return primes;
}

vector<int> sieve_segment(long long L, long long R) {
    long long limit = sqrt(R);
    auto primes = simple_primes(limit);
    vector<bool> is_prime(R - L + 1, true);
    for (long long p : primes) {
        long long start = max(p * p, ((L + p - 1) / p) * p);
        for (long long j = start; j <= R; j += p)
            is_prime[j - L] = false;
    }
    vector<int> result;
    for (long long i = L; i <= R; i++) {
        if (i > 1 && is_prime[i - L]) result.push_back((int)i);
    }
    return result;
}

int main() {
    long long L = 1, R = 30;
    auto primes = sieve_segment(L, R);
    for (int p : primes) cout << p << " ";
    cout << "\n";
}

📑 Small prime list

        
long long limit = sqrt(R);
auto primes = simple_primes(limit);

We want to find primes in the range [L, R].
For this, only small prime numbers up to sqrt(R) are sufficient.
Those small primes are found with the simple_primes function.

🗂️ Separate prime table for the range

        
      
vector<bool> is_prime(R - L + 1, true);

This array represents only the range [L, R].
For example, if L=10, R=20, the array size is 11 and corresponds to real numbers with the logic i-L.

✖️ Marking factors with small primes

        
      
long long start = max(p * p, ((L + p - 1) / p) * p);
for (long long j = start; j <= R; j += p)
    is_prime[j - L] = false;

The critical part here is where to start marking from.
p*p -> no need to mark multiples of each prime before its own square (because they would have already been eliminated by smaller prime factors).
((L + p - 1) / p) * p -> the first multiple of p in the range [L, R] is found.
The larger of the two is chosen (max) -> the correct starting point is guaranteed.
Then, factors are eliminated by advancing with j += p.

📋 Collecting primes

        
      
for (long long i = L; i <= R; i++) {
    if (i > 1 && is_prime[i - L]) result.push_back((int)i);
}

Prime numbers in the range [L, R] are added to the result vector.
i > 1 check -> because 1 is not prime.

🧩 Algorithm

Segmented sieve is suitable for working with very large numbers.
Advantage:
- The is_prime array only holds the range [L, R] -> memory saving.
- For very large R values, we don’t have to store the entire 0..R array.
Small primes are found once -> then used only in the range.

Time Complexity: O((R − L + 1) log log R)
Memory Complexity: O(R − L + 1)

💻 Let’s Run It

        
      
[fr0stb1rd@archlinux demo]$ nano sieve_segment.cpp
[fr0stb1rd@archlinux demo]$ g++ sieve_segment.cpp -o sieve_segment -O2
[fr0stb1rd@archlinux demo]$ ./sieve_segment 
2 3 5 7 11 13 17 19 23 29 
[fr0stb1rd@archlinux demo]$ 

⏱️ Benchmarks

        
      
[fr0stb1rd@archlinux demo]$ hyperfine \
  --shell=none \
  --warmup 5 \
  -r 5000 \
  './sieve_simple > /dev/null' \
  './sieve_odd > /dev/null' \
  './sieve_wheel > /dev/null' \
  './sieve_segment > /dev/null' 

Benchmark 1: ./sieve_simple > /dev/null
  Time (mean ± σ):       1.6 ms ±   0.3 ms    [User: 0.9 ms, System: 0.6 ms]
  Range (min … max):     0.7 ms …   2.7 ms    5000 runs
 
Benchmark 2: ./sieve_odd > /dev/null
  Time (mean ± σ):       1.6 ms ±   0.3 ms    [User: 0.9 ms, System: 0.6 ms]
  Range (min … max):     0.6 ms …   2.9 ms    5000 runs
 
Benchmark 3: ./sieve_wheel > /dev/null
  Time (mean ± σ):       1.3 ms ±   0.5 ms    [User: 0.7 ms, System: 0.5 ms]
  Range (min … max):     0.7 ms …   2.5 ms    5000 runs
 
Benchmark 4: ./sieve_segment > /dev/null
  Time (mean ± σ):     924.1 µs ± 264.0 µs    [User: 512.2 µs, System: 346.1 µs]
  Range (min … max):   681.6 µs … 3699.5 µs    5000 runs
 
Summary
  ./sieve_segment > /dev/null ran
    1.36 ± 0.63 times faster than ./sieve_wheel > /dev/null
    1.71 ± 0.61 times faster than ./sieve_odd > /dev/null
    1.74 ± 0.60 times faster than ./sieve_simple > /dev/null
[fr0stb1rd@archlinux demo]$ 

⚡ Performance Comparison

We tested four different implementations of the Sieve of Eratosthenes on the same number range and measured their execution times with Hyperfine. In the measurements, the output was not printed to the screen (> /dev/null), and each method was run 5000 times.

Method	Average Time	Min - Max
Simple Sieve	1.6 ms	0.7 - 2.7 ms
Odd Sieve	1.6 ms	0.6 - 2.9 ms
Wheel Sieve	1.3 ms	0.7 - 2.5 ms
Segmented Sieve	924 µs	682 - 3700 µs

🔍 Analysis

sieve_simple and sieve_odd run at very similar speeds; small optimizations (sieving over odd numbers) did not make a big difference.
With sieve_wheel, eliminating some numbers from the start reduced the execution time with about 20% speed gain.
Segmented Sieve was the fastest method due to its range-based operation; it is about 1.7 times faster than the others.

💡 Note: Small deviations (σ) and min/max values can be observed in the measurements because CPU timing and system load can have minor effects. The differences become much more pronounced in large number ranges.

📊 Graph

🚀 Other Methods and Advanced Optimizations

There are a few more methods used, especially for large number ranges or situations requiring high performance.

1️⃣ Bitset-Based Sieve

std::bitset or manual bit arrays are used instead of vector<bool>.
Memory usage is significantly reduced because only 1 bit is needed for each number.
Provides a CPU cache advantage for large n values and improves speed.

2️⃣ Sieve of Atkin

A modern prime number sieve.
Quickly identifies prime candidates with specific modular equations.
Can be faster than the classic Sieve of Eratosthenes for very large numbers.
Disadvantage: The algorithm is more complex and difficult to implement.

3️⃣ Parallel / GPU-Assisted Sieve

The sieve is applied simultaneously on a multi-core CPU or GPU.
Provides speed gains for huge ranges when combined with segmented or wheel versions.
Example: GPU-accelerated implementations with CUDA or OpenCL.

4️⃣ Cache-Optimized Sieve

Arranges memory accesses to be CPU cache-friendly.
Reduces the memory access latency of the classic sieve for large n values.
Technically closely related to the segmented sieve but performs finer cache segmentation.

5️⃣ Advanced Wheel Sieve

Larger wheels can be used by going beyond the 6k ± 1 rule.
Examples:
- Wheel based on 30 -> excludes primes 2, 3, 5.
- Wheel based on 210 -> excludes primes 2, 3, 5, 7.
Goal: To reduce the constant factor for large ranges by sieving over fewer numbers.

6️⃣ Pre-calculated Primes (Memoization)

In frequently used ranges or applications, small prime numbers are pre-calculated and stored.
Example: The range [2, 10^6] is calculated once and reused in subsequent operations.
This eliminates the need for recalculation in the same range.

7️⃣ Analytic / Test-Based Methods

Although not a sieve, prime checks can be performed on large single numbers with Miller-Rabin or AKS primality tests.
Used especially in situations where individual prime checks are needed.

📋 Comparison Table

Method	Memory Usage	Time Complexity	Feature / Advantage
Simple Sieve	O(n)	O(n log log n)	Simple and understandable
Odd Sieve	≈ O(n/2)	O(n log log n)	Memory saving over odd numbers
Wheel Sieve (6k ± 1)	O(n)	O(n log log n)	Smaller constant factor, faster
Advanced Wheel Sieve	O(n)	O(n log log n)	Less elimination with larger wheels (30, 210 based)
Segmented Sieve	O(R-L+1)	O((R-L+1) log log R)	Memory saving for large ranges
Bitset Sieve	O(n/8)	O(n log log n)	Significantly reduces memory usage
Sieve of Atkin	O(n)	O(n) theoretical / fast in practice	Faster than classic Sieve for very large numbers
Parallel / GPU Sieve	O(R-L+1)	Depends on hardware and segment size	Processes large ranges simultaneously and quickly
Cache-Optimized Sieve	O(R-L+1)	Depends on hardware and segment size	Optimized for CPU cache, for large `n`
Pre-calculated (Memo)	Depends on app	Reuse is fast	Time saving for frequent ranges
Analytic / Test-Based	O(1)	O(k) or O(log n)	Miller-Rabin, AKS primality tests, individual checks

📚 Glossary

🟢 Prime Number

Natural numbers greater than 1 that have no divisors other than 1 and themselves.
Example: 2, 3, 5, 7, 11, 13 …

🔴 Composite Number

A number greater than 1 that is not prime.
That is, it has at least two different divisors.
Example: 4 (2×2), 6 (2×3), 9 (3×3).

🧺 Sieve

An algorithmic approach that systematically eliminates non-primes.
The name comes from the idea of “sifting” out the eliminated numbers.