Wyznaczanie liczb pierwszych – Sito Eratostenesa

Liczby pierwsze od dawna interesują matematyków oraz hakerów. Są one bowiem wykorzystywane do szyfrowania różnego rodzaju newralgicznych danych takich jak hasła czy numery karty kredytowych. Z nastaniem ery elektroniki ich znaczenie znacznie we współczesnej matematyce znacznie wzrosło. Liczba pierwsza jest liczbą naturalną większa o jedynki i mającą dokładnie dwa dzielniki: 1 oraz samą siebie. Do liczb pierwszych należą: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41… Jak widać nie ma żadnej zależności pomiędzy kolejnymi cyframi. Co więcej operując na coraz większych cyfrach będziemy znajdować coraz mniej liczb pierwszych.

Sito Eratostenesa

Lista kroków:

Krok 1:  Ustaw wszystkie elementy tablicy liczb na true

Krok 2: i ← 2;  

Krok 3: Jeśli i ≥ n, to idź do kroku 11;

Krok 4: w ← i + i;

Krok 5: Jeśli w > n, to idź do kroku 9;

Krok 6: Tablica[w] ← false;

Krok 7:  w ← w + i;

Krok 8:  Idź do kroku 5;

Krok 9:  i ← i + 1;

Krok 10: Idź do kroku 3;

Krok 11: i ← 2;

Krok 12: Jeśli i > n, to zakończ;

Krok 13: Jeśli T[i] = true, to pisz i;

Krok 14: i ← i + 1;            

Krok 15: Idź do kroku 12;

Pascal:

C#:

C++:

Fot: Wikipedia.

,