Clasa a IX-a · Frecvență, sume parțiale și ciurul lui EratosteneRead in English

Ciurul lui Eratostene în C++

În engleză: Sieve of Eratosthenes

O(n log n)C++1747 de linii1 exemplu

Ideea

Găsește toate numerele prime până la n. Pornim cu toate numerele nemarcate; pentru fiecare i nemarcat (deci prim) marcăm ca neprimi multiplii lui, începând de la i * i (multiplii mai mici au fost deja marcați de factori mai mici). Ajunge să mergem cu i cât timp i * i <= n. ciur[x] = true înseamnă că x NU este prim.

Descrierea în engleză

Finds all prime numbers up to n. We start with all numbers unmarked; for every unmarked i (hence prime) we mark its multiples as not prime, starting from i * i (smaller multiples were already marked by smaller factors). It is enough to go on with i while i * i <= n. ciur[x] = true means x is NOT prime.

Complexitate
O(n log log n)
Clasa
Clasa a IX-a (Grade 9)

Exemple

Exemplul 1

Intrare

30

Ieșire așteptată

2 3 5 7 11 13 17 19 23 29

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

ciurul-lui-eratostene.cpp
/*
 * Titlu: Ciurul lui Eratostene
 * Clasa: 9
 * Capitol: Frecvență, sume parțiale și ciurul lui Eratostene
 * Descriere: Găsește toate numerele prime până la n. Pornim cu toate numerele
 *            nemarcate; pentru fiecare i nemarcat (deci prim) marcăm ca neprimi
 *            multiplii lui, începând de la i * i (multiplii mai mici au fost deja
 *            marcați de factori mai mici). Ajunge să mergem cu i cât timp i * i <= n.
 *            ciur[x] = true înseamnă că x NU este prim.
 * Complexitate: O(n log log n)
 *
 * Exemplu
 * Intrare: 30
 * Ieșire: 2 3 5 7 11 13 17 19 23 29
 */
#include <iostream>
using namespace std;

const int NMAX = 1000000;
bool ciur[NMAX + 1];

int main()
{
    int n;
    cin >> n;
    ciur[0] = ciur[1] = true;
    for (int i = 2; i * i <= n; i++)
    {
        if (!ciur[i])
        {
            for (int j = i * i; j <= n; j = j + i)
            {
                ciur[j] = true;
            }
        }
    }
    for (int i = 2; i <= n; i++)
    {
        if (!ciur[i])
        {
            cout << i << ' ';
        }
    }
    cout << '\n';
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.