[Algorithm] Prime Test (Uji Bilangan Prima)
Categories: Programming | April 30th, 2008 | by Felix J | 9 Comments |Kenalkah anda dengan bilangan yang disebut dengan bilangan “Prima” ?? Saya yakin anda mengetahui dan mengenal apa itu bilangan “Prima”…
Apa itu bilangan “Prima”? Sebuah bilangan bisa dikatakan bilangan “Prima” apabila bilangan tersebut hanya dapat di bagi oleh bilangan itu sendiri dan angka ‘1′…. contohna kita ambil contoh saja dengan bilangan ‘5′.. mari kita liat bilangan ‘5′ apakah prima atau tidak… (Nb: Pengecekan dimulai dari angka 2)
5 % 2 = 1
5 % 3 = 2
5 % 4 = 1
5 % 5 = 0
Sekarang, terbukti bahwa angka 5 adalah bilangan prima karena hanya habis dibagi oleh angka itu sendiri… bagi yang mendalami komputer, pasti akan tau tanda ‘%’ itu adalah ‘modulo’ (sisa pembagian)
Ok, enough with the introduction… sebenarnya Prime Test Algorithm ini sebenarnya bisa kita implementasikan dengan berbagai cara. Salah satunya adalah cara ‘naif’ (naive) yang meng-loop dari angka 2 (bahkan ada yang memulai dari angka 1. No problem) sampai angka itu sendiri, dan jika sebelum angka itu sudah terdapat angka yang habis dibagi, maka itu bukan bilangan prima. contohnya adalah dengan kode seperti ini :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include<stdio.h> int main() { int n,flag=1; scanf("%d", &n); for (int i=2; i<n; i++) { if (n%i==0) { printf("Bukan Prima\n"); flag = 0; break; } } if (flag) printf("Prima\n"); return 0; } |
yah… cara diatas sangat naif… langsung tembak. dan pasti benar… 
*hanya jika bilangan2 kecil… :P* bagaimana jika input saya berikan menjadi di atas jutaan? saya yakin dengan algoritma diatas, hasil yang akan keluar pasti sangat lambat…
Bagaimana cara mengoptimisasi cara pengecekan tersebut? Baiklah, kita mulai dari berbagai ‘properties’ bilangan prima itu sendiri… yang dapat kita simpulkan dari sebuah bilangan prima adalah sebagai berikut :
- Bilangan Prima adalah Bilangan Ganjil kecuali angka ‘2′
- Angka 2 adalah Bilangan Prima
- Angka 1 adalah bukan Bilangan Prima
Setelah melihat di atas, maka dapat kita buat kode untuk mengecek bilangan itu lebih efisien lg menjadi seperti ini :
1 2 3 4 5 6 7 8 9 10 11 12 13 | int is_prime(int n) { if (n==1) return 0; if (n==2) return 1; if (n%2==0) return 0; for (int i=3; i<n; i+=2) { if (n%i==0) return 0; } return 1; } |
Sampai disini, ternyata algoritma ini sudah cukup cepat… tapi tetap saja kurang cepat untuk berbagai bilangan diatas jutaan… bagaimana kita mengoptimisasinya lagi? jawabannya adalah kita hanya mengecek hanya sampai pada akar dari bilangan tersebut… mengapa demikian? karena angka yang melebihi akar dari bilangan tersebut sudah pasti tidak akan dapat membagi bilangan tersebut… *untuk yang satu ini, silahkan anda buktikan sendiri :)*
dengan begitu, kita dapat memperbaharui kode tersebut menjadi :
1 2 3 4 5 6 7 8 9 10 11 12 13 | int is_prime(int n) { if (n==1) return 0; if (n==2) return 1; if (n%2==0) return 0; for (int i=3; (i*i) <= n; i+=2) { if (n%i==0) return 0; } return 1; } |
bisa kita liat disitu ada (i*i) yang dimaksud dengan ini adalah akarnya. Misal 25, maka akarnya adalah 5, dengan dijalankan kode diatas, terlihat i*i = 25… jadi statement diatas hanya merupakan restatement dari sqrt(n) saja. bedanya, disini tidak melibatkan floating number…
*Updated*
Karena kesalahan saya yang melupakan bahwa kode diatas dapat overflow jika n mencapai batas integer, maka dengan update ini, saya akan mengupdate kode diatas sehingga jika terdapat n yang sampai ke batas integer pun tidak masalah. Kode dibawah ini saya tambahkan karena diingatkan oleh Bp. Suhendry. *Terima Kasih om Shu…*
1 2 3 4 5 6 7 8 9 10 11 12 | int is_prime(int n) { if (n==1) return 0; if (n==2) return 1; if (n%2==0) return 0; for (int i=3; i <= n/i; i+=2) { if (n%i==0) return 0; } return 1; |
Kode diatas ini, akan lebih lambat. Karena yang seperti Bp. Suhendry bilang bahwa cost operasi pembagian lebih besar dari perkalian.
dengan kode terakhir yang diatas, anda dapat melakukan pengujian bilangan prima lebih cepat 25x dari kode naif semula..
Akhir kata, semoga tutorial ini bermanfaat untuk anda. *Kritik dan Saran dipersilahkan.. :)*
- Felix J
) hehehe….
huhuhu…