Pada Java, untuk menentukan apakah suatu bilangan adalah prima, biasanya dilakukan pengecekan dengan membagi bilangan tersebut dengan angka dari 2 hingga n-1. Artikel ini menyajikan cara yang lebih efisien, yaitu dengan memeriksa hingga akar kuadrat (sqrt) dari n dan memanfaatkan pola 6k±1.
Dengan menggunakan Stream, kita dapat menerapkan lazy evaluation, yang memungkinkan kita untuk menghasilkan Stream bilangan prima yang hanya melakukan operasi ketika elemen dibutuhkan.
Dengan menerapkan perbaikan dan penggunaan Stream yang disajikan, Anda dapat mengimplementasikan algoritma penentuan bilangan prima yang lebih efisien.
Secara umum, untuk memeriksa apakah n adalah bilangan prima, kita membagi n dengan angka dari 2 hingga n - 1 dan memeriksa apakah hasilnya habis dibagi.
Dalam metode ini, mari kita terapkan beberapa pengoptimalan untuk meningkatkan efisiensi dan menerapkan evaluasi malas (lazy evaluation) menggunakan Stream.
Metode Naif
Berikut adalah metode naif untuk memeriksa apakah n adalah bilangan prima.
Peningkatan
Jika n = a x b, kita dapat berasumsi bahwa a > b tanpa mengurangi tingkat keumuman. Artinya, kita hanya perlu memeriksa hingga akar kuadrat dari n (sqrt(n)). Karena operasi sqrt() mahal, kita dapat menggantinya dengan kondisi i * i <= n.
Bilangan prima yang lebih besar dari 5 memiliki bentuk 6k ± 1. Oleh karena itu, kita dapat mengurangi jumlah pemeriksaan dengan meningkatkan i sebanyak 6.
Metode yang Ditingkatkan
Menerapkan Evaluasi Malas dengan Stream
Stream di Java berbeda dengan List, di mana operasi tidak langsung dieksekusi saat didefinisikan.
Stream hanya mendefinisikan cara menghitung setiap elemen dan menunggu hingga elemen tertentu diperlukan, lalu hanya melakukan operasi untuk mendapatkan elemen tersebut.
Dengan memanfaatkan hal ini, kita dapat membuat Stream untuk menghasilkan bilangan prima seperti berikut.