← All examples

Sieve of Eratosthenes

C++ Algorithms

primes up to n

Flowchart (ISO 5807)

YesNoYesNoStartInput ni = 0, n, 1prime[i] = truep = 2, p * p <= n, p++prime[p]i = p * p, n, pprime[i] = falsei = 2, n, 1prime[i]Output i « »EndFigure 1 — sieve

Source code

void sieve(int n) {
    bool prime[100];
    for (int i = 0; i <= n; i++) prime[i] = true;
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p) prime[i] = false;
        }
    }
    for (int i = 2; i <= n; i++) {
        if (prime[i]) cout << i << " ";
    }
}