Sieve of Eratosthenes

Pseudocode

• Input: An integer
• Output: All prime numbers from to
• Algorithm: Sieve of Eratosthenes
  • let A be an array of boolean values, indexed by integers to , initially all set to true.
  • for not exceeding , to
    • if A[i] is true:
      • for not exceeding
        • set A[j] to false

C++ Implementation

See Computer Science/Programming/Arrays

#include <algorithm>
#include <vector>

using std::vector;

vector<bool> sieve(largest);
std::fill(sieve.begin(), sieve.end(), true);

for (uint increment = 2; increment < int(sqrt(largest)) + 1; increment++) {
    if (sieve[increment]) {
        uint index = 0;

        while ((increment * increment) + increment * index < largest) {
            sieve[(increment * increment) + increment * index] = false;
            index++;
        }
    }
}

vector<uint> primes;

for (uint i = 0; i < sieve.size(); i++) {
    if (sieve[i] && !(i == 0 || i == 1)) {
        primes.push_back(i);
    }
}

C Implementation

// Arrume array of only 1s
void sieve(int array[], int length) {
    // We can avoid sqrt by using
{ #2}

    for (int increment = 2; increment * increment < length + 1; increment ++) {
        // Strike out multiples
        if (array[increment]) {
            int index = 0;

            while ((increment * increment) + increment * index < length) {
                array[(increment * increment) + increment * index] = 0;
                index++;
            }
        }
    }
}

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    // NOTE: Variable Length Arrays at runtime not stored in the heap are very bad
    int a[n + 1];
    
    sieve(a, n);
    
    for (int i = 0; i < n; i++) {
        if (a[i]) {
            printf("%d\n", i);
        }
    }

    return 0;
}

Python Implementation

sieve = [True] * largest

for increment in range(2, int(sqrt(largest)) + 1):
    if sieve[increment]:
        index = 0
    
        while (increment ** 2) + increment * index < largest:
            sieve[(increment ** 2) + increment * index] = False
            index += 1

# Prime numbers from 0 - the largest input
primes = [i for i in range(len(sieve)) if sieve[i] and i not in [0, 1]]