RTDPGRL38VJZZ
Grafika przedstawia namalowane kredkami cyfry w różnych kolorach oraz różnej wielkości.

I_R_W14_M24_Java Sito Eratostenesa czyli łowca liczb pierwszych

Źródło: wygenerowany przez sztuczną inteligencję Canva.ai, domena publiczna.

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).

1
Ćwiczenie 1

Napisz program, który wygeneruje liczby pierwsze z zakresu od 1 do 30.

RF9SA2SV2AVZ2