Pemeriksa Primalitas Suatu Bilangan Menggunakan Pemrograman Dinamis - Mulyana, Teady Matius Surya; Wijaya, Agustinus Frits; Ginting, Jusia Amanda; Lee, Francka Sakti; Alvaro, Giovanni (Computatio : Journal of Computer Science and Information Systems, 2025)
Bilangan prima merupakan bilangan yang sangat penting dalam berbagai bidang komputasi. Sebagai bilangan yang tidak habis terbagi bilangan manapun selain 1 dan bilangan itu sendiri, sehingga sering dimanfaatkan pada pengkodean yang memerlukan bilangan unik. Salah satu masalah yang timbul sehubungna dengan keperluan bilangan prima ini adalah untuk mendapatkan suatu bilangan unik yang prima memerlukan pengujian primalitas bilangan. Pemeriksaan primalitas dapat mengintegrasikan prinsip Dynamic Programming (DP) melalui teknik memoization dan penyimpanan data persisten. Proses ini akan memanfaatkan tabel bilangan prima yang tersimpan sehingga dapat digunakan Kembali pada pengujian bilangan primalitas bilangan berikutnya. Pendekatan trial division, memungkinkan sistem untuk secara menyimpan dan menggunakan kembali hasil komputasi sebelumnya, sehingga mempercepat proses pemeriksaan bilangan prima di masa mendatang. Uji coba pembagian dioptimalkan dengan batas akar kuadrat. Melalui serangkaian pengujian kinerja, hasil menunjukkan peningkatan efisiensi yang signifikan. Waktu eksekusi berkurang drastis ketika bilangan yang diperiksa sudah ada dalam tabel memoized atau berada dalam jangkauan bilangan prima yang telah dibangun sebelumnya. Namun, penelitian ini juga mengidentifikasi keterbatasan kinerja yang substansial. Ketika program dihadapkan pada kebutuhan untuk memperluas tabel ke rentang bilangan yang sangat besar, algoritma uji coba pembagian sekuensial yang digunakan untuk perluasan tabel menjadi tidak optimal dan memakan waktu komputasi yang sangat lama.