Mencari bilangan prima menurutku adalah menu wajib bagi seorang programmer newbie yang ingin mengasah kemampuan algoritmanya. Mengapa? Karena dalam algoritma bilangan prima inilah, aku dulu menyadari betapa pentingnya 'setiap detik' dalam proses eksekusi program. Hehehe. Dalam artikel ini, kita akan membahas beberapa teknik-teknik algoritma untuk menentukan apakah suatu bilangan termasuk dalam bilangan prima atau bukan, beserta optimasi coding yang bisa dilakukan.

Definisi bilangan prima adalah bilangan yang lebih besar dari satu dan hanya mempunyai dua faktor, yaitu angka satu dan dirinya sendiri. Dari definisi ini, kita dapat menentukan apakah suatu bilangan termasuk bilangan prima atau bukan, dengan cara mencari faktor bilangan tersebut selain angka satu dan dirinya sendiri. Bila bilangan tersebut tidak mempunyai faktor selain satu dan dirinya sendiri, maka bilangan itu prima. Mudah ya!?

Sieve of Erathosenes

Sebelum memulai koding, alangkah baiknya kita membahas suatu teknik yang konon lebih cepat dan efisien untuk menentukan bilangan prima. Yaitu dengan menggunakan algoritma Sieve of Erathosenes. Namun, dalam artikel ini, kita tidak akan membahas implementasi kodenya. Mengapa? Karena, implementasi kodenya mau tidak mau harus bersinggungan dengan array, maka tidak cocok untuk programmer gadungan seperti diriku. Xixixi. Tapi tak usah kuatir, aku akan membahas sedikit konsepnya, yah berhubung aku masih seorang pg, maka akan kubahas sebisaku. Maaf kalau ada yang salah.

Misal kita akan mencari bilangan prima antara 1-100, maka langkah pertama adalah kita mencatat angka 1-100, misal kita menggunakan kertas. Karena angka 1 tidak memenuhi definisi bilangan prima, maka kita coret angka tersebut. Kemudian, angka berikutnya, yaitu angka 2, akan dianggap sebagai bilangan prima. Selanjutnya, kita coret semua kelipatan dari angka 2 ini, yaitu 4, 6, 8, 10, hingga angka 100, karena pasti bukan bilangan prima.

Kemudian, bilangan berikutnya setelah angka 2, yang belum tercoret, yaitu angka 3, pasti bilangan prima. Seperti langkah sebelumnya, coret semua kelipatan dari 3. Begitu seterusnya, sehingga pada akhirnya akan terdapat 25 bilangan yang belum tercoret. Dan bilangan-bilangan itulah bilangan prima pada range 1-100.

Kembali ke Laptop

Seperti yang sudah kita bahas sebelumnya, untuk menentukan bilangan prima, maka kita cukup mencari faktor lain dari bilangan tersebut, selain angka satu dan bilangan tersebut. Untuk mencari faktor suatu bilangan x, algoritma yang umum digunakan adalah dengan membrute-force dari 1 hingga x/2. Berikut contoh script dalam javascript untuk menentukan bilangan prima dengan cara mencari faktor-faktor dari suatu bilangan x.

function CekPrima(x){
	if(x==1) return false;
	if(x==2 || x==3) return true;
	else
		//brute force sampai x/2
		for(var i=2; i <= Math.ceil(x/2); i++)
			if(x%i == 0)
				return false;
	return true;
}

Fungsi dalam javascript di atas adalah algoritma yang sering kutemui di dalam buku-buku pemrograman. Baik itu dalam bahasa C, C++, PHP, Pascal, Delphi, VB, VB.NET, JAVA, dlsb. Padahal coding di atas masih bisa dioptimasi. Entah mengapa para penulis buku pemrograman masih menggunakan algoritma di atas. Mungkin karena konteks bukunya adalah buku pemrograman bagi orang yang ingin belajar pemrograman dari nol, sehingga tidak ingin terlalu njlimet. Kalau buku algoritma mungkin lain ceritanya kali ya? Tau ah gelap.

Nah, sebenarnya, untuk menentukan bilangan prima, kita cukup me-brute force hingga akar dari bilangan tersebut. Kalau mencari faktor, mau tidak mau memang kita harus me-brute force hingga x/2, namun kalau cuman untuk mencari bilangan prima, kita cukup looping hingga akar x. Kok bisa? Seperti yang kukatakan di awal, dalam pemrograman, setiap detik (ehem, bahkan tiap milidetik) begitu berharga. Silakan dicorat-coret di kertas, mengapa kok cukup sampai akar x, hihihi. Berikut fungsi yang lebih baik daripada fungsi sebelumnya.

function CekPrima(x){
	if(x==1) return false;
	if(x==2 || x==3) return true;
	else
		//brute force sampai sqrt(x)
		for(var i=2; I <= Math.ceil(Math.sqrt(x)); i++)
			if(x%i == 0)
				return false;
	return true;
}

Mungkinkah dioptimasi lagi? Hmm, masih bisa. Misal kita ingin menentukan bilangan pada range 1-100, apakah prima atau bukan, sebenarnya kita cukup melakukan operasi mod sebanyak 4 kali, yaitu x mod 2, x mod 3, x mod 5, dan x mod 7. Misal untuk menentukan bilangan 97, kalau pakai cara sebelumnya, kita harus melakukan looping operasi mod sampai 10 kali. Padahal sebenarnya cuman butuh 4 kali. Berikut contoh implementasinya.

function CekPrima(x){
	//untuk x = 1-100
	if(x==1) return false;
	if(x==2 || x==3 || x==5 || x==7) return true;
	if(x%2==0) return false;
	if(x%3==0) return false;
	if(x%5==0) return false;
	if(x%7==0) return false;
	if(x<100) return true;
	//untuk x lebih dari 100
	for(var i=8; I <= Math.ceil(Math.sqrt(x)); i++)
		if(x%i == 0)
			return false;
	return true;
}

Fungsi di atas memerlukan pengecekan operasi mod hingga 4 kali, untuk x <= 100. Untuk x > 100, maka kita akan menggunakan cara sqrt yang telah kita bahas sebelumnya. Kekurangan dari algoritma ini adalah kita harus menentukan batas bilangan prima yang akan digunakan untuk operasi mod untuk range bilangan tertentu. Misal kalau range 1-100, maka batasnya 7, sedang kalau range 1-100000 batasnya adalah 313. Jadi, bisa dibilang cara mix ini merupakan algoritma yang tidak murni lagi. Karena angka-angka prima yang digunakan sebagai batas sudah diketahui. Hehehe.

Namun, dari algoritma inilah, aku mengambil pelajaran berharga dalam dunia pemrograman, bahwa coding yang lebih panjang belum tentu akan menjadi lebih lambat, serta begitu berharganya waktu yang digunakan untuk satu kali looping. Thanks to Mr Rudi Kurniadi, pak dosen Struktur Data di STMIK ProVisi Semarang, yang telah memberikan pencerahan.

Manakah Algoritma yang Lebih Efisien?

Silakan lakukan percobaan berikut. Masukkan angka di dalam textbox, trus klik salah satu tombol yang ada. Group 3 tombol pertama berfungsi untuk menentukan bilangan dalam textbox itu prima atau bukan, sedang group 3 tombol berikutnya untuk mencari jumlah bilangan prima yang terdapat dari range 1-x, di mana x adalah angka di dalam textbox. Tombol dengan label 'Cara mix' mengimplementasikan cara ke-3 (yang kita bahas paling akhir), 'Cara bruteforce sqrt(x)' mengimplementasikan cara ke-2, sedang 'Cara bruteforce x/2' untuk cara ke-1.

Untuk lebih memudahkan dalam melakukan percobaan, silakan masukkan angka 99991, 999983, 1234567891, kemudian klik group tombol pertama. Dari hasil percobaanku (semoga hasilnya sama d:), dapat kusimpulkan, bahwa cara mix dan cara sqrt(x) cukup seimbang. Kadang cara mix lebih cepat, kadang cara sqrt(x) lebih unggul. Sedang cara x/2, pasti sudah tahu perbedaannya kan?

Nah, selanjutnya, kita akan mencari jumlah bilangan prima dalam range 1-x. Berdasarkan pengujian yang kulakukan di sahabat sejatiku, yaitu komputer berotak pentium III, dapat kusimpulkan bahwa cara mix jauh lebih unggul dibanding kedua cara lainnya. Silakan masukkan angka 1000-100000. Dan klik tombol-tombol yang ada di group ke-2.

Bagaimana? Apakah hasilnya sama? Bila iya, maka dapat kita simpulkan, jika ingin menentukan suatu bilangan adalah prima atau bukan, lebih efisien bila menggunakan cara sqrt(x), sedang bila ingin mencari jumlah bilangan prima dalam range tertentu, kita dapat menggunakan cara mix. Dalam percobaan ini, batas bilangan prima untuk pengecekan pada cara mix adalah 313, atau sampai range 100000.

Lain waktu, insya Allah kita akan membahas tentang Sieve of Erathosenes, yang jauh lebih murni daripada cara mix ini. Hehe. Mengapa Sieve of Erathosenes? Karena teknik Sieve of Erathosenes ini konon juga lebih optimal untuk mencari jumlah bilangan prima dalam suatu range, namun tidak bijak jika hanya untuk menentukan satu bilangan prima saja.

Semoga bermanfaat. Tetap dalam perdjoeangan!! Happy Coding!!