[Java] Prímszámok hatékony generálása Stream segítségével

Általában egy n szám prímszám-e, azt úgy ellenőrizzük, hogy 2-től n - 1-ig osztjuk n-nel, és megnézzük, hogy osztható-e maradék nélkül.

Ebben a módszerben néhány optimalizálást alkalmazunk a hatékonyság javítása érdekében, és a Stream-et használjuk a lusta kiértékelés (lazy evaluation) alkalmazásához.

Naiv módszer

Az alábbiakban egy naiv módszert mutatunk be az n szám prímszám-e vizsgálatára.

Javítások

• Ha n = a x b, akkor feltételezhetjük, hogy a > b anélkül, hogy elveszítenénk az általánosságot.
  Vagyis i-nek csak sqrt(n)-ig kell ellenőrizni. A sqrt() művelet költséges, ezért helyettesíthetjük az i * i <= n feltétellel.
• Az 5-nél nagyobb prímszámok 6k ± 1 alakúak. Ezért i-t 6-tal növelve ellenőrizhetjük, csökkentve az ellenőrzések számát.

Javított módszer

Lusta kiértékelés (Lazy Evaluation) alkalmazása Stream-mel

A Java Stream-je, ellentétben a List-tel, nem azonnal hajtja végre a műveleteket, amikor azok meg vannak határozva.

Az egyes elemek kiszámításának módja meghatározva van, de a rendszer várakozik, amíg egy adott elemre szükség van, és csak akkor hajtja végre az adott elem kiszámításához szükséges műveleteket.

Ezt kihasználva a következőképpen hozhatunk létre egy Stream-et a prímszámok generálására.

Futtatási eredmény

Teljes kód

Futtatási eredmény