Prime Number

minggu lalu waktu kuliah TBD “teknologi Basis Data“, mas poleng (baca : Pak Arif Wibisono ^^) sempat ngobrol sejenak mengenai Java, Sun , Oracle untuk sedikit intermesso di sela kuliah. nah, disitu sempat disinggung “apa cara yang paling cepat menghitung bilangan prima?“, beberapa suara bersautan pelan (pura2 denger ^^ bisikan2 hati biar lebih dramatis) antara membagi bilangan N dengan x = 1~N, ada yang menyaut bilangan N dibagi x = 1~(N/2). kusendiri dulu (dulu banget pas alpro) make yang kedua ^_^

nah, dosen muda SI ini lalu bilang, “N dan n/2 masih kelamaan, jawabnya sqrt(N)” :) persisnya ga ngomong gitu, lebih kocak :D tapi karena pikiran terlanjur memproses sqrt(N) jadi ga inget detail :) jadi ingat kata pak Rully, dan juga mastri (mastery, masih ingatkah kau bilang pake sqrt(N) aja dan jangan kebanyakan make nested conditional waktu di thread programming lautan lama ;) )

nah abis gitu mr dosen nyelotek, coba buktikan. karena awalnya aku rada ga konsen kuliah (berangkat buru2 tuh, datang telat lagi).. so masih skeptis dulu.. baru sampe rumah kepikiran lagi, coba deh liat2 ^_^ dan dan memang terbukti ;)
sekaligus untuk menyegarkan kembali ingatan yang udah lama ngga ngoding dan berhubungan ama algoritma, jadi pengen nulis hasil penalaranku dan bikin codingnya :) he5x kayaknya bakal berguna juga nih buat praktikan alpro 1 (angkatan 2007) saat ini. kali aja keluar (dan biasanya emang keluar ^^)

ke, saatnya mulai. mungkin metodologi pembuktianku lebih agak2 ke arah analogi teoritis di awal kemudian menggunakan pembuktian (aduh apa namanya, di diskrit tuh) tapi ga ku lanjutin pake rumus2nya (membuktikan kasus n berlaku untuk N+1) :) males ja ngitung dan nulis, semua berjalan di RAM (baca : kepala doank) jadi volatile dan ga disimpen :p

as we know, tiap bilangan N memiliki faktor2 yang membentuk pasangan perkalian X dan Y. jumlah X dan Y bisa dikit, bisa banyak banget, tergantung besar nilai N kan :) so, secara umum faktor N adalah X1~Xn dan Y1~Yn. yang mau aku tunjukin disini adalah pola ‘unik’ pasangan faktor tersebut, lanjutannya mending langsung pake contoh aja, faktor 100 adalah :

1×100
2×50
4×25
5×20
10×10
20×5
25×4
50×2
100×1

ehm… bisa ngeliat pola ‘unik’ tersebut ???
oke, gimana kalo disusun kayak gini :

1×100 100×1
2×50 50×2
4×25 25×4
5×20 20×5
10×10

kalo kalian berpikir “X kayak cermin-nya Y“, bener ^_^ kalo nilai2 tersebut diletakkan pada koordinat cartesius (benernya aku mau bikinin grafik cartesiusnya, cuman ga sempat) bakal terlihat bahwa kurva yang dihasilkan simetris (jika dipotong dnegan garis x=y) dengan nilai extrem pada 10×10 (dengan kata lain X=Y).
nah apa hubungannya dengan pendapat diatas mengenai efisiensi penggunaan sqrt(N) sebagai limit perhitungan penentuan bilangan prima ? X*Y=N, (X=Y)=> X2=N => X=sqrt(N) ;)

yah, itu contohnya kan angka 100, angka yang bulat, gampang keliatan, apa teori diatas juag berlaku untuk yang ngga bulat (kotak mungkin ^^)
sepp, pertanyaan bagus, cek mau angka berapa, kita ambil 39 aja gimana :)
faktornya :

1×39 39×1
3×13 13×1

nah loh, ga ada X=Y -nya yah???

^_^ memang keliatannya seperti itu disini, tapi kalo di grafik cartesius bakal ada ko’, tepatnya di nilai 6,244997998…. panjang deh :D tapi, kalo kita bicara mengenai bilangan prima, kita bicara di domain bilangan asli, bilangan yang dimulai dari 1 ~ tak hingga dan BULAT, atau tanpa pecahan. dalam bilangan asli dapat dipastikan floor rounding atau dibulatkan kebawah, sehingga sehingga dapat diasumsikan dengan aman bahwa limit sqrt(N) yang dipakai adalah 6. tidak perlu dilakukan pengecekan modulo dengan pembagi lebih dari 6 (bandingkan dengan mengecek semua 39 pembagi)

so ngapain nyari lagi modulo dengan x (pembagi perhitungan) > sqrt(N), karena perkalian dengan nilai diatas itu PASTI merupakan ‘cermin’ dari perkalian faktor sebelumnya yang telah dihitung, lebih baik menghemat waktu kan ^_^ 100 sih masih enak, coba kalo ngitung apakah 100000000 itu prima, kan menghabiskan waktu.
oke, 100000000 emang bukan prima, udah dilihat juga tau ^_^ tapi coba cek 98165512531247, tes prima pa bukan :D

nah cukup segitu aja pembuktiannya ala tyo yang ngga jelas tersebut ^_^

coba rubah aja code limit menjadi N atau (N/2) kalo mau ngetes, bandingkan hasil bilangan yang ditampilkan ;) pengecekan silahkan sampe berapa suku bilangan prima deh, 1 juta juga gpp, makin banyak makin menegaskan kalo yang ditampilkan sama berarti bener kan :) dan perbedaan kecepatan bakal kerasa, yang lebih cepat tentu dengan menggunakan sqrt(N) ;)

NB : kalo ada yang keliru atau salah mohon kritik dan sarannya ;)

App jadinya :

Free Image Hosting at www.ImageShack.us