Pendahuluan

Bilangan prima merupakan suatu bilangan yang dapat dikatakan antik, karena sulit kita tentukan suatu deret yang akan menghasilkan bilangan prima. Dalam situs wikipedia disebutkan definisi dari bilangan prima, yaitu “bilangan prima adalah bilangan asli yang lebih besar dari 1, yang faktor pembaginya adalah 1 dan bilangan itu sendiri.” sebagai contoh misalkan bilangan 2, bilangan ini hanya mempunyai dua faktor yaitu 1 dan 2. Sepuluh bilangan prima yang pertama adalah 2, 3, 5, 7, 11, 13, 17, 19, 23 dan 29. sedangkan bilangan yang tidak termasuk bilangan prima dinamakan bilangan komposit.

Algoritma Mencari Bilangan Prima

Algoritma dalam mencari bilangan prima ada banyak sekali, namun dalam paper ini kita hanya akan membahas 3 algoritma saja.

1. Algoritma yang pertama adalah sebagai berikut:
   1. Start
   2. Read N
   3. iJum = 0
   4. for i:=1 to N do
   5. if ( N mod i = 0) then
   6. iJum++
   7. end if
   8. end for
   9. if (iJum = 2) then return true
   10. else return false
   11. finish

   Algoritma diatas nilai kompleksitasnya adalah 3n+4 termasuk O(n) atau linear time

2. Algoritma yang kedua adalah:
   1. Start
   2. Read N
   3. iJum = 0
   4. for i:=2 to (N-1) do
   5. if (N mod i == 0)
   6. iJum++
   7. end if
   8. end for
   9. if (iJum=2) then return true
   10. else return false
   11. end if
   12. finish

   Algoritma diatas nilai kompleksitasnya adalah 3n-2 termasuk O(n) atau linear time.

3. Algoritma yang ketiga adalah:
   1. Start
   2. Read N
   3. bPrima = true
   4. for i:=2 to ( sqrt(N) ) do
   5. if (N mod i == 0)
   6. bPrima = false
   7. break
   8. end if
   9. end for
   10. return bPrima
   11. finish

   Algoritma diatas nilai kompleksitasnya adalah termasuk O( ).

fungsi mencari waktu running

Bila kita melihat nilai kompleksitas dari masing-masing algoritma diatas maka algoritma yang ketiga terlihat lebih sedikit memakan waktu running. Untuk lebih jelasnya akan kita coba membuat program dengan menggunakan bahasa Java.

Fungsi yang digunakan untuk mendapatkan waktu running proses adalah


long startTime = System.currentTimeMillis();
--- kode program yang akan dites ---;
long endTime = System.currentTimeMillis();


spesifikasi hardware dan software

Spesifikasi komputer dan software yang digunakan adalah sebagai berikut:

• Sistem operasi : Microsoft Windows Vista
• Prosesor : Intel Core Duo CPU T2350 (@ 1,86 Ghz)
• Memory : 1014 MB
• Versi Java : Java 6 update 14
• Editor : JCreator v 3.50

Metode Pengujian

Dalam pengujian kali ini kita akan sedikit merubah alur algoritma diatas. Algoritma tersebut akan kita gunakan sebagai suatu method untuk mengecek apakah bilangan N adalah bilangan prima atau bukan. Pada program kali ini kita akan mencari bilangan prima antara 1 hingga M, dengan asumsi M = 5000 (1<= M <=5000).

Pengujian untuk setiap algoritma akan kita lakukan sebanyak 3 kali dan kita ambil rata-rata waktu running yang dibutuhkan.

Contoh program yang akan digunakan sebagai penguji adalah sebagai berikut:


public class BilPrima_1
{
boolean isPrime(int n)
{
int i, iJum = 0;
for(i=1;i<=n;i++) if(n%i==0) iJum++; if (iJum==2) return true; else return false; } public static void main(String[] args) { int i; int m; BilPrima_1 obj = new BilPrima_1(); m = 5000; long startTime = System.currentTimeMillis(); for(i=1;i<=m;i++) if(obj.isPrime(i)) System.out.print(i+" "); long endTime = System.currentTimeMillis(); System.out.println("\nWaktu Eksekusi = "+(endTime-startTime)+" ms"); } }

Pengujian

1. Algoritma pertama

   Program yang digunakan adalah sebagai berikut

   
public class BilPrima_1
{
boolean isPrime(int n)
{
int i, iJum = 0;
for(i=1;i<=n;i++) if(n%i==0) iJum++; if (iJum==2) return true; else return false; } public static void main(String[] args) { int i; int m; BilPrima_1 obj = new BilPrima_1(); m = 5000; long startTime = System.currentTimeMillis(); for(i=1;i<=m;i++) if(obj.isPrime(i)) System.out.print(i+" "); long endTime = System.currentTimeMillis(); System.out.println("\nWaktu Eksekusi = "+(endTime-startTime)+" ms"); } }

   Hasil pengujian adalah seperti dalam tabel dibawah ini:

   Pengujian ke-	Hasil running time (ms)
   Ke-1	140
   Ke-2	140
   Ke-3	141
   Rata-rata	140,33

2. Algoritma kedua

   Program yang digunakan adalah sebagai berikut

   
public class BilPrima_2
{
boolean isPrime(int n)
{
int i, iJum = 0;
for(i=2;i<=n-1;i++) if(n%i==0) iJum++; if (iJum==2) return true; else return false; } public static void main(String[] args) { int i; int m; BilPrima_1 obj = new BilPrima_1(); m = 5000; long startTime = System.currentTimeMillis(); for(i=1;i<=m;i++) if(obj.isPrime(i)) System.out.print(i+" "); long endTime = System.currentTimeMillis(); System.out.println("\nWaktu Eksekusi = "+(endTime-startTime)+" ms"); } }

   Hasil pengujian adalah seperti dalam tabel dibawah ini:

   Pengujian ke-	Hasil running time (ms)
   Ke-1	140
   Ke-2	140
   Ke-3	140
   Rata-rata	140

3. Algoritma ketiga

   Program yang digunakan adalah sebagai berikut

   
public class BilPrima_3
{
boolean isPrime(int n)
{
int i;
boolean bPrime = true;
for(i=2;i<=Math.sqrt(n);i++) if(n%i==0) { bPrime = false; break; } return bPrime; } public static void main(String[] args) { int i; int m; BilPrima_1 obj = new BilPrima_1(); m = 5000; long startTime = System.currentTimeMillis(); for(i=1;i<=m;i++) if(obj.isPrime(i)) System.out.print(i+" "); long endTime = System.currentTimeMillis(); System.out.println("\nWaktu Eksekusi = "+(endTime-startTime)+" ms"); } }

   Hasil pengujian adalah seperti dalam tabel dibawah ini:

   Pengujian ke-	Hasil running time (ms)
   Ke-1	141
   Ke-2	140
   Ke-3	141
   Rata-rata	140,66

Kesimpulan

Berdasarkan hasil pengujian diatas terlihat perbedaan yang terjadi tidak terlalu signifikan, karena berdasar time complexity ketiga algoritma tersebut adalah sama O(n).

Daftar Pusaka

• www.wikipedia.com
• Java Manual