Algorytmy - Sito Erastostenesa

 A Sito Erastotenesa

Co to jest sito Eratostenesa?

Sito Eratostenesa jest algorytmem, który szybko znajduje wszystkie liczby pierwsze z przedziału [2..n] . Inaczej mówiąc, przesiewa z tego zbioru liczby, w taki sposób, że zostają tylko pierwsze.

Sito Eratostenesa – działanie 

Działanie algorytmu jest bardzo proste. Pobieramy najpierw liczbę n od użytkownika. Następnie tworzymy tablicę n-elementową, indeksowaną od 2 (bo to najmniejsza spośród liczb pierwszych), a następnie wartość każdej komórki w tablicy ustawiamy na prawdę. Bierzemy najmniejszy indeks (czyli dwa) i ustawiamy wartości wszystkich komórek, których indeksy są wielokrotnościami dwójki na fałsz. W dalszej kolejności postępujemy tak z następnym niewykreślonym indeksem, czyli trójką i analogicznie jak w przypadku dwójki ustawiamy wartości komórek o indeksach równych k*3 na fałsz.

W ten sposób postępujemy, dopóki obierany indeks będzie mniejszy lub równy pierwiastkowi z n. Dlaczego tak? Dlaczego do pierwiastka z n? Wynika to z tego, że liczba ma tyle samo dzielników mniejszych od tego pierwiastka, co większych od niego.

Sito Eratostenesa (film) | Test pierwszości

Kod programu Sito Erastotenesa -w edytorze online

Przykład implementacji:

#include <iostream>

#include <cmath>

using namespace std;

void sito(int n)

{

bool *tablica=new bool[n+1];

for(int i=2; i<=n; i++) tablica[i]=true;

//wypełniamy tablicę wartościami logicznymi true

for(int i=2; i<=sqrt(n); i++)

{

if(tablica[i]==true)

for(int j=i*i; j<=n; j+=i) tablica[j]=false;

//jeśli indeks jest wielokrotnością innego indeksu to ustawiamy

// jego wartośćna fałsz

}

cout << "Liczby pierwsze, nalezace do przedzialu [2," << n << "] to: " << endl;

for(int i=2; i<=n; i++)

{

if(tablica[i]==true) cout << i << endl;

}

delete [] tablica;

}

int main()

{

int x;

cout << "Podaj interesujacy Cie zakres ";

cin >> x;

sito(x);

return 0;

}