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 rozmiarzen+1.Pętla inicjalizująca: wypełniamy tablicę wartościami
true.Warunek stopu: zgodnie z optymalizacją, zamiast obliczać pierwiastek funkcją
Math.sqrt(n), stosujemy waruneki * 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.