Sito Eratostenesa

Dawno dawno temu (prawie 300 lat przed naszą erą) w starożytnej Grecji żył sobie Pan o imieniu Eratostenes. Zajmował się geografią, astronomią oraz matematyką. Prawdopodobnie to właśnie Eratostenes podał też prosty sposób na wyznaczanie liczb pierwszych. Sposób ten zwykło się nazywać sitem Eratostenesa, my wykorzystamy go do napisania programu, który za nas będzie wyznaczał liczby pierwsze.

Liczby pierwsze

Zacznijmy od przypomnienia sobie, co to jest liczba pierwsza? Jakie cechy musi spełniać liczba, by móc nazywać ją liczbą pierwszą?

Liczba pierwsza to taka liczba naturalna większa od 1, która ma tylko dwa dzielniki, czyli dzieli się tylko przez dwie liczby: przez 1 i przez samą siebie.

Liczbami (większymi od 1), które dzielą się tylko przez 1 i przez samą siebie są np.: 2, 3, 5, 7, 11, 13, 17, 19 itd.

Sito Eratostenesa

Sposób wyznaczania liczb pierwszych zaproponowany przez Eratostenesa jest dość prosty. Załóżmy, że chcemy wyznaczyć liczby pierwsze mniejsze niż 100 (czyli mamy zbiór liczb od 2 do 100). Początkowo możemy nawet zacząć od przećwiczenia podanego sposobu na kartce papieru. Nie potrzebujemy do tego komputera. Zaczynamy więc od wypisania 100 liczb na kartce.

Eratostenes mówi tak: wybierz najmniejszą liczbę, czyli 2 i wykreśl wszystkie wielokrotności liczby 2 większe od niej samej, czyli np. 4, 6, 8, 10, 12, 14, 16 itd. Następnie znów wybierz kolejną najmniejszą liczbę, czyli 3 i wykreśl jej wielokrotności (6, 9, 12, 15, 18, 21 itd.). Część z nich może być już oczywiście wykreślona wcześniej, ale to nic nie szkodzi. Po wykreśleniu wszystkich wielokrotności liczby 3, wybieramy kolejną liczbę – tym razem będzie to 5, bo 4 zostało już wcześniej wykreślone i wykreślamy jej wielokrotności (10, 15, 20, 25, 30 itd.).

Powtarzamy czynność wykreślania wielokrotności aż dojdziemy do końca tabeli. Po wykreśleniu wszystkich okaże się, że te liczby które zostały, to właśnie są liczby pierwsze. Niewykreślone powinny pozostać: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 i 97.

Program

Program warto zacząć od zadeklarowania sobie zmiennej, w której przechowywać będziemy zakres liczb, w którym chcemy poszukiwać liczb pierwszych. Dzięki temu łatwo, w jednym miejscu dokonamy zmiany, na podstawie której program będzie wiedział, jakiej maksymalnie liczby pierwszej ma szukać. Początek będzie wyglądał więc tak:

package pl.Fincon;

public class Main {

    public static void main(String[] args) {

        // zakres, czyli maksymalna liczba do której będziemy szukać liczb pierwszych
        int zakres = 100;
    }
}

Następnie zdefiniujemy tablicę elementów typu boolean (przechowujących wartość true lub false), która będzie w programie czymś w rodzaju tabelki, którą rysowaliśmy powyżej na papierze analizując algorytm.

/**
 * tablica liczb pierwszych
 * liczbą pierwszą będzie taka liczba n, dla której pierwsze[n] == true
 */
boolean pierwsze[] = new boolean[zakres];

Dlaczego jest to tablica boolean-ów a nie liczb całkowitych? W zasadzie nie ma to większego znaczenia. Po prostu umawiamy się, że n będzie liczbą pierwszą, jeśli element tablicy o indeksie n będzie miał wartość true (czyli pierwsze[n] == true).

Po zdefiniowaniu tablicy trzeba zadbać o jej wypełnienie wartościami. Tablicę wypełnimy w całości wartościami true, bo na początku nie wiemy jeszcze, która liczba będzie liczbą pierwszą, a która nie. Wykreślanie wielokrotności będzie polegało na zmianie wartości elementu z true na false. Do szybkiego wypełnienia tablicy boolean-ów skorzystamy z metody w klasie Arrays.

// na początek całą tablicę wypełnimy wartościami true
Arrays.fill(pierwsze, true);

Po wykonaniu powyższej instrukcji, każdy element tablicy będzie miał wartość true.

Liczby pierwsze to zgodnie z definicją liczby naturalne większe od 1. Teoretycznie powinniśmy to uwzględnić w indeksowaniu naszej tablicy, ale dla ułatwienia sobie zadania możemy przyjąć pewne uproszczenie. Po prostu liczby 0 i 1 od razu wykreślimy, bo na pewno nie są liczbami pierwszymi:

// od razu pomijamy liczby 0 i 1, bo na pewno nie są liczbami pierwszymi
pierwsze[0] = false;
pierwsze[1] = false;

Czas na najważniejszy kawałek programu, czyli pętle, w której będziemy przesuwać się po tablicy w poszukiwaniu kolejnych liczb. Indeksowanie pętli zaczynamy od 2, bo 2 będzie najmniejszą liczbą pierwszą, a skończymy na wartości określonej w zmiennej o nazwie zakres.

for (int i = 2; i < zakres; i++) {
}

Cały czas musimy pamiętać, że w Javie numerowanie pól tablicy zaczyna się od 0, a kończy na wartości o 1 mniejszej niż rozmiar, czyli w naszym przypadku na wartości zakres – 1.

Wewnątrz pętli musimy jakoś spowodować, że wykreślimy wszystkie wielokrotności liczby, którą w danej chwili analizujemy, czyli liczby wskazywanej przez licznik i. Aby to zrobić użyjemy drugiej pętli. Jedna pętla znajduje się wewnątrz drugiej, więc uwaga na nawiasy klamrowe!

for (int i = 2; i < zakres; i++) {

    // wykreślamy wszystkie wielokrotności liczby i (najmniejsza wielokrotność to i+i)
    for (int j = i + i; j < zakres; j = j + i) {
        pierwsze[j] = false;
    }
}

Przeanalizujmy, co robi wewnętrzna pętla FOR. Dla każdej wartości i rozpoczynamy nową pętlę startując od wartości i + i (int j = i + i).

i + i to po prostu najmniejsza wielokrotność liczby i. Po każdym przebiegu drugiej pętli modyfikujemy wartość licznika j dodając do niego i. Dodając za każdym razem tę samą liczbę i spowodujemy, że wyliczymy kolejną wielokrotność liczby i.

Np. dodając ciągle do siebie liczbę 3 znajdujemy kolejne wielokrotności liczby 3:

3 + 3 = 6
3 + 3 + 3 = 9
3 + 3 + 3 + 3 = 12
3 + 3 + 3 + 3 + 3 = 15
i tak dalej...

Skoro potrafimy znaleźć w pętli wszystkie wielokrotności analizowanej liczby, to z algorytmu Eratostenesa wiadomo, że wszystkie te wielokrotoności należy wykreślić. Wykreślić, czyli w naszym przypadku ustawić elementom wartość false.

Po zakończeniu programu w tablicy zostaną tylko liczby pierwsze. Dla przypomnienia liczbami pierwszymi w naszym programie będą te liczby, dla których elementy tablicy mają wartość false.

Na koniec – aby przekonać się, że program działa prawidłowo – trzeba tylko wyświetlić na ekranie te elementy tablicy, które nie zostały wykreślone, więc mają wartość true. Przy wyświetlaniu pomijamy elementy z wartościami false, bo są to liczby przez nas wykreślone, a więc liczby, które nie są liczbami pierwszymi.

// na koniec wyświetlamy wyniki, czyli tylko te elementy tablicy, które mają wartość true
for (int i = 0; i < pierwsze.length; i++) {
    if (pierwsze[i] == true) {
        System.out.println(i);
    }
}

Nasz program można nieznacznie usprawnić, przez co obliczenia będą odbywały się szybciej. Zauważamy, nie ma potrzeby wykreślania liczby, która została już wcześniej wykreślona. Nie dość, że nie trzeba jej wykreślać, to jeszcze nie ma potrzeby wyszukiwania wszystkich jej wielokrotności, bo one na pewno też już wcześniej zostały wykreślone.

Dodajemy w tym celu jedną instrukcję IF, sprawdzającą czy analizowana liczba nie jest już przypadkiem wykreślona.

for (int i = 2; i < zakres; i++) {

    // analizujemy tylko te liczby, które nie zostały jeszcze wykreślone
    if (pierwsze[i] == true) {

        // wykreślamy wszystkie wielokrotności liczby i (najmniejsza wielokrotność to i+i)
        for (int j = i + i; j < zakres; j = j + i) {
            pierwsze[j] = false;
        }
    }
}

Cały kod programu powinien wyglądać tak:

package pl.Fincon;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {

        // zakres, czyli maksymalna liczba do której będziemy szukać liczb pierwszych
        int zakres = 100;

        /**
         * tablica liczb pierwszych
         * liczbą pierwszą będzie taka liczba n, dla której pierwsze[n] == true
         */
        boolean pierwsze[] = new boolean[zakres];

        // na początek całą tablicę wypełnimy wartościami true
        Arrays.fill(pierwsze, true);

        // od razu pomijamy liczby 0 i 1, bo na pewno nie są liczbami pierwszymi
        pierwsze[0] = false;
        pierwsze[1] = false;

        for (int i = 2; i < zakres; i++) {

            // analizujemy tylko te liczby, które nie zostały jeszcze wykreślone
            if (pierwsze[i] == true) {

                // wykreślamy wszystkie wielokrotności liczby i (najmniejsza wielokrotność to i+i)
                for (int j = i + i; j < zakres; j = j + i) {
                    pierwsze[j] = false;
                }
            }
        }

        // na koniec wyświetlamy wyniki, czyli tylko te elementy tablicy, które mają wartość true
        for (int i = 0; i < pierwsze.length; i++) {
            if (pierwsze[i]) {
                System.out.println(i);
            }
        }
    }
}

Po uruchomieniu programu na ekranie powinny zostać wyświetlone tylko liczby pierwsze.

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

Aby wyznaczyć liczby pierwsze większe niż 100 wystarczy zmienić wartość zmiennej zakres zdefiniowanej na początku programu.

PermaLink: https://java.kozlowski.photos/2017/04/sito-eratostenesa/