PENGGUNAAN BASIS DATA DALAM IMPLEMENTASI ALGORITME SIEVE OF ERATOSTHENES

DITO SATRIO WICAKSONO, Dr. Eng. Silmi Fauziati, S.T., M.T.; Indriana Hidayah, S.T., M.T.

2016 | Skripsi | S1 TEKNOLOGI INFORMASI

Bilangan Prima merupakan salah satu bilangan penting dalam ilmu matematika. Selain merupakan bilangan yang banyak diteliti dalam ilmu murni, bilangan prima juga memegang peran penting dalam bidang kriptografi dan keamanan data. Sieve of Eratosthenes merupakan salah satu algoritme dasar yang digunakan dalam proses penyaringan bilangan prima. Meskipun sederhana dan banyak digunakan, namun algoritme ini memiliki kelemahan berupa konsumsi memori primernya yang besar. Keterbatasan RAM menyebabkan algoritme ini kurang dapat diandalkan untuk mengolah masukan yang sangat besar. Penelitian ini mencoba mengatasi masalah tersebut dengan menawarkan implementasi alternatif dari algoritme Sieve of Eratosthenes. Pada penelitian ini, memori sekunder berupa basis data dimanfaatkan untuk mengatasi masalah keterbatasan RAM yang dimiliki implementasi standar dari algoritme Sieve of Eratosthenes. Penelitian ini juga membandingkan unjuk kerja dari implementasi standar algoritme Sieve of Eratosthenes dengan implementasi algoritme tersebut yang menggunakan basis data. Hasil penelitian menunjukkan bahwa penggunaan basis data dalam implementasi algoritme Sieve of Eratosthenes mampu mengatasi masalah keterbatasan RAM yang dihadapi implementasi standar dari algoritme tersebut. Kedua pendekatan implementasi basis data yang dilakukan terbukti mampu mengolah masukan yang lebih besar dibanding masukan terbesar yang dapat ditangani oleh implementasi standar. Pada implementasi dengan pendekatan rekursi, konsumsi RAM dapat ditekan secara signifikan. Meskipun demikian, penggunaan basis data membuat waktu eksekusi program menjadi lebih lama. Selain itu, pemanfaatan bilangan prima yang tersimpan di dalam basis data untuk mengurangi waktu eksekusi program pada penelitian ini terbukti tidak berhasil.

Prime number is one of the most important numbers in mathematics. On top of being intensively studied within the realm of pure science, primes also hold prominent position in cryptography and data security. Sieve of Eratosthenes is one of basic algorithm for prime generating. Despite of its simplicity and popularity, the algorithm’s shortcome lies in its big primary memory consumption. RAM limitation makes this algorithm less dependable for handling very large input. In order to tackle the problem, this research tried to offer an alternative way for Sieve of Eratosthenes implementation. On this research, database as secondary memory was used to overcome RAM limitation problem that bound the standard implementation of Sieve of Eratosthenes. This research also compared the performance of standard implementation of Sieve of Eratosthenes and the performance of the same algorithm that incorporate database on its implementation. This research shows that the inclusion of database into Sieve of Algorithm implementation can solve RAM limitation problem that hamper the standard implementation of the same algorithm. Both database implementation approaches can successfully handle larger input than the largest input that the standard implementation could handle. On the implementation with recursion approach, RAM consumption can be reduced significantly. However, database implementation makes execution time of the program longer. Moreover, using the primes stored in the database to reduce the execution time of the program was proven unsuccessful.

Kata Kunci : bilangan prima, penyaringan bilangan prima, algoritme, Sieve of Eratosthenes, Basis Data