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:

program sito eratostenesa;
const n = 100;
var
tablica : array[2..n] of boolean;
i, w : integer;
 
begin
  for i := 2 to n do tablica[i] := true;
 
  i := 1;
  repeat
    i := i + 1;
    w := 2 * i;
      repeat
        tablica[w] := false;
        w := w + i;
      until (w > n);
  until i > sqrt(n);
  for i := 2 to n do
  begin
    if (tablica[i]) then
    write(i, ' ');
  end;
end.

C#:

namespace ConsoleApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 0;
            Console.Write("Podaj liczbe: ");
            n = Convert.ToInt32(Console.ReadLine());
            bool[] tab = new bool[n+1];
            for (int i = 2; i * i <= n; i++)
            {
                if (tab[i] == true)
                {
                    continue;
                }
                for (int j = 2 * i; j <= n; j += i)
                {
                    tab[j] = true;
                }
            }
            Console.WriteLine("Liczby pierwsze z zakresu [0," + n + "]: ");
            for (int i = 2; i <= n; i++)
            {
                if (tab[i] == false)
                {
                    Console.Write(i + " ");
                }
            }
            Console.ReadKey();
        }
    }
}

C++:

#include <iostream>
 
using namespace std;
 
const int n = 100;
bool numbersTable[n + 1];
 
int main()
{
    for (int i = 2; i*i <= n; ++i )
    {
        if (numbersTable[i] == true)
            continue;
        for (int j = 2*i ; j <= n; j += i)
            numbersTable[j] = true;
    }
 
    cout << "Liczby pierwsze z przedziału od 2 do " << n << ":" << endl;
 
    for (int i = 2; i <= n; i++)
        if (numbersTable[i] == false)
            cout << i << endl;
    return 0;
}

Fot: Wikipedia.

liczby pierwsze, Sito Eratostenesa