Dalam artikel Cara Cepat Menentukan Bilangan Prima, telah dibahas algoritma untuk mencari apakah suatu bilangan merupakan bilangan prima atau bukan. Nah, dalam artikel ini akan dibahas mengenai cara yang cukup efektif untuk mencari deret bilangan prima dalam range tertentu. Algoritma yang akan dipakai adalah Sieve of Eratosthenes.

Sekilas Sieve of Eratosthenes

Sieve of Eratosthene adalah algoritma sederhana dan cukup kuno yang digunakan untuk mencari semua bilangan prima hingga range tertentu. Berikut adalah langkah-langkah untuk mencari deret bilangan prima dengan batas range 120. Silakan langsung dicoba dioret-oret di kertas ya, :)

1. Catat semua bilangan dari 1-120.
2. Karena angka 1 tidak memenuhi definisi bilangan prima, maka coret angka tersebut. Kemudian, angka berikutnya, yaitu angka 2, akan dianggap sebagai bilangan prima.
3. Coret semua bilangan yang merupakan kelipatan dari bilangan prima terbesar yang diketahui (pada langkah pertama berarti angka 2). Bilangan tersebut pasti bukan bilangan prima.
4. Bilangan yang belum tercoret setelah angka prima terbesar yang diketahui (pada langkah pertama berarti angka 3), pasti bilangan prima.
5. Ulangi langkah 3 dan 4 hingga tidak ada lagi bilangan yang lebih besar dari bilangan prima terbesar yang diketahui yang belum tercoret.

Hehe, maaf, penjelasannya agak ribet. Silakan lihat ilustrasi dari wikipedia^[1] berikut, semoga dapat membantu memahaminya.

Berikut contoh diagram flowchart SOE. Maaf agak berantakan.

Berikut contoh script SOE dalam javascript. Script berikut merupakan hasil konversi script SOE dalam bahasa C dari Marcus Kazmierczak^[2]

function SOE(maxRange)
{
	var START = 3;
	var STOP = maxRange;
	var nap;	// not-a-prime, boolean untuk mengetahui apakah merupakan bilangan prima
	var c;		// untuk menyimpan jumlah bilangan prima, sebagai pointer untuk menyimpan bilangan prima ke-n
	var prime = new Array();	// array untuk menyimpan bilangan prima

	prime[0] = 2;	// dimulai dari bilangan 2 adalah prima
	c = 1;			// jumlah bilangan prima saat ini = 1

	// cukup mengecek bilangan ganjil
	for (var num=START; num<=STOP; num+=2)
	{
		nap = false;  // anggap sebagai prima dulu

		for (var i=0; i<c; i++)
		{
			// cek apakah num habis dibagi dengan bilangan prima yg telah diketahui,
			// bila habis dibagi, maka num bukan bilangan prima
			if ((num % prime[i]) == 0) { nap = true; break; }

			// hentikan looping bila kuadrat bilangan prima ke-i lebih besar dari num
			if ((prime[i] * prime[i]) > num) { break; }
			// bisa juga pakai cara ini:
			// hentikan looping bila bilangan prima ke-i lebih besar dari akar num
			//if (prime[i] > Math.sqrt(num)) { break; }
		}

		// jika num adalah bilangan prima, simpan ke array bilangan prima yg telah diketahui
		if (nap !== true)
		{
			prime[c] = num; c++;
		}
	}
	return prime;
}

Uji Coba

Silakan gunakan test sederhana berikut untuk mengetahui manakah yang lebih efisien, pencarian bilangan prima menggunakan SOE atau menggunakan cara biasa.

Kesimpulan

Dari percobaan yang kulakukan, cara SOE lebih cepat daripada pencarian biasa. Untuk pencarian hingga range 1000000, cara SOE membutuhkan waktu rata-rata 500 milidetik, sedang pencarian menggunakan cara biasa membutuhkan waktu rata-rata 3 detik. Terima kasih telah membaca, semoga bermanfaat, Happy Coding!!

• http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
• http://mkaz.com/math/primes/prime_numbers.html