:~$ newsletter --subscribe
cat ~/artykuly/algorytmy/wyznaczanie-liczb-pierwszych-sito-eratostenesa.md

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 we współczesnej matematyce znacznie wzrosło. Liczba pierwsza jest liczbą naturalną większą od 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 liczbami. Co więcej operując na coraz większych liczbach 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:

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#:

csharp
using System;

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++:

cpp
#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;
}

Python:

Ta sama zasada w Pythonie, gdzie dzięki listom składanym zapis jest wyjątkowo zwięzły. Tym razem True oznacza liczbę pierwszą, zgodnie z listą kroków opisaną na początku:

python
def sito_eratostenesa(n):
    liczby = [True] * (n + 1)
    liczby[0] = liczby[1] = False          # 0 i 1 nie sa pierwsze

    for i in range(2, int(n ** 0.5) + 1):  # wystarczy do pierwiastka z n
        if liczby[i]:
            for j in range(i * i, n + 1, i):
                liczby[j] = False           # wykreslamy wielokrotnosci i

    return [i for i, pierwsza in enumerate(liczby) if pierwsza]


print(sito_eratostenesa(100))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Dlaczego sito jest tak szybkie?

Zwróćmy uwagę na dwie optymalizacje, które pojawiają się we wszystkich powyższych implementacjach. Po pierwsze zewnętrzną pętlę prowadzimy tylko do pierwiastka z n (i * i <= n). Jeśli liczba złożona ma dzielnik większy od pierwiastka, to musi mieć też dzielnik mniejszy, który został już wykreślony wcześniej. Po drugie wykreślanie wielokrotności zaczynamy od i * i, a nie od 2 * i, bo mniejsze wielokrotności (2·i, 3·i…) skreśliły już wcześniejsze liczby pierwsze.

Dzięki temu złożoność obliczeniowa sita wynosi O(n log log n), w praktyce niemal liniowo względem n. To znacznie szybciej niż sprawdzanie podzielności każdej liczby z osobna, dlatego sito Eratostenesa pozostaje najpopularniejszą metodą wyznaczania wszystkich liczb pierwszych z danego zakresu.

Java:

java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

    public static List<Integer> sitoEratostenesa(int n) {
        boolean[] pierwsza = new boolean[n + 1];
        Arrays.fill(pierwsza, true);
        pierwsza[0] = pierwsza[1] = false;

        for (int i = 2; i * i <= n; i++)
            if (pierwsza[i])
                for (int j = i * i; j <= n; j += i)
                    pierwsza[j] = false;

        List<Integer> wynik = new ArrayList<>();
        for (int i = 2; i <= n; i++)
            if (pierwsza[i]) wynik.add(i);
        return wynik;
    }

    public static void main(String[] args) {
        System.out.println(sitoEratostenesa(100));
    }
}
udostępnij: ·
Łukasz Dudziński
Łukasz Dudziński · założyciel i autor
Pasjonat informatyki, a zwłaszcza programowania. Zwariowany maniak na tle nowych technologii oraz komputerów. W wolnych chwilach bloger... więcej-o-mnie →
ls ~/artykuly/powiazane --limit 3
komentarze --count 0
rss dla komentarzy →

// brak komentarzy — bądź pierwszy

dodaj-komentarz

Komentarze są moderowane. Podane dane przetwarzamy wyłącznie w celu publikacji komentarza (polityka prywatności).