← Усі приклади

Решето Ератосфена

C++ Алгоритми

прості до n

Блок-схема за ДСТУ

ТакНіТакНіПочатокВвід ni = 0, n, 1prime[i] = truep = 2, p * p <= n, p++prime[p]i = p * p, n, pprime[i] = falsei = 2, n, 1prime[i]Вивід i « »КінецьРисунок 1 — sieve

Вихідний код

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 << " ";
    }
}