Eratostenovo sito

Eratostenovo sito je algoritam za brzo pronalaženje svih prostih brojeva do datog broja n. Umesto da svaki broj posebno proveravamo da li je prost, sito u jednom prolazu „prosejava” ceo niz brojeva i uklanja one koji nisu prosti.

Problem koji rešavamo:

---

Naivno rešenje: provera svakog broja

Problem se može rešiti tako što prođemo kroz sve brojeve od 1 do n i za svaki posebno proverimo da li je prost. Delioce je dovoljno ispitivati do √n (detaljno objašnjenje je na strani Prosti brojevi i faktorizacija).

#include <iostream>
using namespace std;

// Proverava da li je broj n prost (ispituje delioce do korena iz n)
bool isProst(long long n)
{
    if (n < 2)              // 0 i 1 nisu prosti brojevi
        return false;

    long long d = 2;
    while (d * d <= n)      // dovoljno je ići do korena iz n
    {
        if (n % d == 0)     // pronađen delilac, broj nije prost
            return false;
        d = d + 1;
    }
    return true;
}

int main()
{
    int n;
    cin >> n;

    // Za svaki broj od 1 do n posebno proveravamo da li je prost
    for (int i = 1; i <= n; i++)
    {
        if (isProst(i))
            cout << i << endl;
    }

    return 0;
}

Za svaki broj i ovaj program radi oko √i provera, pa je ukupna složenost približno O(n·√n). Za veliko n to je presporo, jer se iste deljivosti proveravaju iznova za svaki broj. Pravo ubrzanje dobijamo pomoću Eratostenovog sita.

---

Ideja algoritma

Sito se zasniva na ideji da u jednom prolazu proveravamo više brojeva odjednom. Pretpostavimo da je n = 50, tj. da treba odrediti sve proste brojeve između 1 i 50:

Uzimamo prvi prost broj, a to je 2, i iz niza uklanjamo sve brojeve veće od 2 koji su deljivi sa 2. Oni sigurno nisu prosti, jer pored 1 i sebe imaju i delilac 2. Posle uklanjanja sadržalaca broja 2 stanje je sledeće:

Postupak ponavljamo sa sledećim neuklonjenim brojem. Ako broj prethodno nije uklonjen, to znači da je prost. Sledeći takav broj je 3, pa uklanjamo sve brojeve veće od 3 koji su deljivi sa 3:

Broj 4 je već uklonjen, pa je sledeći prost broj 5. Uklanjamo brojeve veće od 5 koji su deljivi sa 5:

Ostaje da se uklone brojevi veći od 7 koji su deljivi sa 7. U ovom primeru to je samo broj 49:

Sledeći prost broj je 11, ali je 11 · 11 = 121 > 50, pa se postupak završava. Brojevi koji su ostali su prosti brojevi.

---

Implementacija (C++)

Za pamćenje preostalih brojeva koristimo logički niz P: P[x] == true znači da broj x nije uklonjen. Na početku sve brojeve od 2 do n postavljamo na true, a 0 i 1 na false, jer nisu prosti.

#include <iostream>
using namespace std;

const int DIM = 1000000;   // najveće n za koje program radi

bool P[DIM + 1];           // P[x] == true znači da x (još uvek) smatramo prostim

void eratosten(int n)
{
    // Na početku sve brojeve od 2 do n smatramo prostim.
    // Brojevi 0 i 1 nisu prosti.
    P[0] = false;
    P[1] = false;
    for (int i = 2; i <= n; i++)
    {
        P[i] = true;
    }

    // Delioce ispitujemo samo do korena iz n (i * i <= n).
    for (int i = 2; i * i <= n; i++)
    {
        if (P[i])   // i nije uklonjen, dakle i je prost
        {
            // Uklanjamo sadržaoce broja i: i*i, i*(i+1), ..., do n.
            // Sadržaoce manje od i*i već su uklonili manji prosti brojevi.
            for (int j = i; j <= n / i; j++)
            {
                P[i * j] = false;
            }
        }
    }
}

int main()
{
    int n;
    cin >> n;

    eratosten(n);

    // Ispisujemo brojeve koji nisu uklonjeni
    for (int i = 2; i <= n; i++)
    {
        if (P[i])
            cout << i << endl;
    }

    return 0;
}

Objašnjenje važnih delova

• Spoljašnja petlja ide dok je i * i <= n. Ako je P[i] i dalje true, broj i nije uklonjen nijednim manjim prostim brojem, pa je i sam prost.
• Unutrašnja petlja uklanja brojeve i·i, i·(i+1), ..., i·(n/i). Brojevi između i i i·i već su uklonjeni manjim prostim deliocima (na primer, 2·7 = 14 uklonio je broj 2), pa ih ne treba ponovo proveravati.
• Za delilac i uklanja se n/i − i + 1 brojeva. Za n = 50 i i = 2 to je 25 − 2 + 1 = 24 broja: 4, 6, 8, ..., 50.
• Broj uklanjanja ukupno iznosi oko n/2 + n/3 + n/5 + ..., što daje složenost O(n log log n), praktično skoro linearnu.

---

Upotreba sita kod faktorizacije

Faktorizacija broja n je njegovo rastavljanje na proste činioce:

n = p1^a1 · p2^a2 · ... · pk^ak

Na primer, 50 = 2^1 · 5^2 = 2 · 5 · 5. Faktorizacija se radi tako što broj delimo njegovim najmanjim prostim deliocem dokle god je to moguće, pa nastavljamo sa ostatkom. Za n = 50:

• najmanji delilac je 2: 50 / 2 = 25, a 25 više nije deljivo sa 2;
• najmanji delilac broja 25 je 5: 25 / 5 = 5, pa 5 / 5 = 1;
• kada dođemo do 1, postupak je završen: 50 = 2 · 5 · 5.

Sito možemo prilagoditi tako da za svaki broj x umesto „uklonjen / nije uklonjen” zapamti njegov najmanji prost delilac D[x]. Tada se svaki broj faktoriše vrlo brzo, jer najmanji delilac samo pročitamo iz niza.

#include <iostream>
using namespace std;

const int DIM = 1000000;

int D[DIM + 1];   // D[x] - najmanji prost delilac broja x
int p[20];        // p[k] - k-ti prost činilac broja koji faktorišemo
int a[20];        // a[k] - koliko puta se p[k] pojavljuje (izložilac)

void eratosten(int n)
{
    // Na početku je svaki broj sam sebi najmanji delilac.
    // Za proste brojeve to ostaje tačno i na kraju.
    for (int i = 1; i <= n; i++)
    {
        D[i] = i;
    }

    for (int i = 2; i * i <= n; i++)
    {
        if (D[i] == i)   // i je prost broj
        {
            for (int j = i; j <= n / i; j++)
            {
                // Broj i*j je deljiv sa i. Ako mu do sada nije
                // pronađen manji delilac, najmanji delilac je i.
                if (D[i] < D[i * j])
                    D[i * j] = D[i];
            }
        }
    }
}

// Rastavlja x na proste činioce; vraća broj različitih činilaca k
int faktorizacija(int x)
{
    int k = 0;
    while (x > 1)
    {
        k = k + 1;
        p[k] = D[x];   // najmanji prost delilac trenutnog x
        a[k] = 0;
        while (x % p[k] == 0)   // deli sa najmanjim deliocem dok može
        {
            x = x / p[k];
            a[k] = a[k] + 1;
        }
    }
    return k;
}

int main()
{
    int n, k;
    cin >> n;

    eratosten(n);   // sito se pravi samo jednom

    // Faktorišemo svaki broj od 2 do n
    for (int i = 2; i <= n; i++)
    {
        k = faktorizacija(i);

        cout << i << " = ";
        for (int j = 1; j <= k; j++)
        {
            cout << p[j] << "^" << a[j];
            if (j != k)
                cout << " * ";
        }
        cout << endl;
    }

    return 0;
}

Objašnjenje

• U prvoj petlji svaki broj postaje sam sebi delilac. Za proste brojeve to ostaje tačno i na kraju.
• Ako broj nije prost, njegov najmanji delilac ga „pronalazi” kao proizvod i·j. Na primer, za broj 8 važi 8 = 2·4, pa je i = 2, j = 4. Na početku je D[8] = 8, a pošto je D[2] = 2 < D[8], postavlja se D[8] = 2. Kasnije veći delilac 4 ne može da ga promeni.
• U funkciji faktorizacija elementi niza p su redom najmanji delioci broja x i ostataka koji nastaju deljenjem. Proces se ponavlja dok x ne postane 1.
• Faktorizacija jednog broja tada traje svega O(log x) koraka. Ovaj pristup je pogodan kada treba faktorisati mnogo brojeva, na primer sve brojeve od 2 do n.

Primer izlaza za n = 50 (poslednja tri reda)

48 = 2^4 * 3^1
49 = 7^2
50 = 2^1 * 5^2

---

Vremenska i prostorna složenost

• Naivna provera svih brojeva: O(n·√n)
• Eratostenovo sito: O(n log log n) vremena i O(n) memorije
• Faktorizacija jednog broja pomoću niza D: O(log x)

---

Veza sa drugim algoritmima

• Prosti brojevi i faktorizacija — provera jednog broja i rastavljanje bez sita
• Određivanje NZD i NZS pomoću Euklidovog algoritma
• Osnovni matematički algoritmi