[Java] Wykorzystanie strumieni do leniwego wyszukiwania liczb pierwszych

Często, aby sprawdzić, czy liczba n jest liczbą pierwszą, dzielimy ją przez liczby od 2 do n - 1 i sprawdzamy, czy jest podzielna.

W tej metodzie zastosujemy kilka optymalizacji, aby ją ulepszyć i zwiększyć wydajność, a także wykorzystamy strumienie (Stream) do implementacji leniwego ewaluacji.

Naiwna metoda

Poniżej przedstawiono naiwną metodę sprawdzania, czy liczba n jest pierwsza.

Ulepszenia

• Jeśli n = a x b, to możemy założyć bez utraty ogólności, że a > b.
  Oznacza to, że i musimy sprawdzać tylko do sqrt(n). Operacja sqrt() jest kosztowna, więc możemy ją zastąpić warunkiem i * i <= n.
• Liczby pierwsze większe od 5 mają postać 6k ± 1. Dlatego możemy zwiększać i o 6 i sprawdzać tylko te liczby, co zmniejsza liczbę iteracji.

Ulepszona metoda

Zastosowanie leniwej ewaluacji za pomocą strumieni (Stream)

Strumienie (Stream) w Javie, w przeciwieństwie do List, nie wykonują operacji natychmiast po ich zdefiniowaniu.

Zamiast tego, pozostają w stanie gotowości, definiując sposób obliczenia każdego elementu, a obliczenia są wykonywane dopiero wtedy, gdy potrzebny jest dany element.

Wykorzystując tę cechę, możemy stworzyć strumień generujący liczby pierwsze w następujący sposób.

Wynik działania

Pełny kod

Wynik działania