I_R_W14_M24_Java Sito Eratostenesa czyli łowca liczb pierwszych
Implementacja algorytmu w języku Java
Przekładając opisany pseudokod na język Java, musimy pamiętać o kilku technicznych aspektach:
Tablica: Deklarujemy tablicę typu boolean. W Javie tablice są indeksowane od 0, więc aby obsłużyć liczbę n, potrzebujemy tablicy o rozmiarze n+1.
Pętla inicjalizująca: Wypełniamy tablicę wartościami true.
Warunek stopu: Zgodnie z optymalizacją, zamiast obliczać pierwiastek funkcją Math.sqrt(n), stosujemy warunek i * i <= n.
Wyjaśnienie kluczowych elementów kodu: Tablica boolean[] T: Pełni rolę naszego „sita”. Jeśli T[i] ma wartość true, oznacza to, że liczba i pozostaje w zbiorze jako potencjalna liczba pierwsza.
Inicjalizacja T[s] = true: Na początku zakładamy optymistycznie, że wszystkie liczby w przedziale są pierwsze.
Zagnieżdżona pętla while:
Zewnętrzna pętla wybiera kolejną liczbę pierwszą.
Wewnętrzna pętla „wykreśla” (ustawia na false) wszystkie jej wielokrotności.
Optymalizacja j = i * i: Nie ma potrzeby wykreślać wielokrotności mniejszych niż kwadrat liczby i (np. dla i=5 nie musimy sprawdzać 10,15,20), ponieważ zostały one już wykreślone przy przetwarzaniu mniejszych liczb pierwszych (2 i 3).
Napisz program, który wygeneruje liczby pierwsze z zakresu od 1 do 30.