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

Advertisements

19 comments on “Prime Number

  1. hmm.. maaf tiba tiba comment.
    tapi agak tertarik masalah bilangan prima.
    mending Generate sekalian aja pake algo ‘Sieve of Erathosenes’ yaitu bikin array dengan jangkauan yang diinginkan bertipe boolean.
    itu paling cepet yang gua tau

  2. Ada yang lebih cepet oom,
    kalo 1-100,
    cukup dibagi ama 2, 3, 5, 7,
    kalo habis, berarti bukan,

    misal 71, kalo pake caranya oom, perlu 8 kali,
    padahal 4 kali aja cukup,

    tapi, ya itu, repot harus nentuin rangenya,

    emang paling gampang dan akurat pake cara sqrt()

    • kasusnya kan udah beda lagi :)

      mencari bilangan prima dalam range tertentu dengan mengetahui apakah bil x prima kan udah beda

      tentunya kalo kasus beda pendekatan juga bisa beda berikut optimasi2nya ;)

      kalo cuman mau me list bilangan prima dalam range tertentu, pake SoE aja, kagak usah brute force kek yang diatas ;)
      =====

      msalah yang lo tulis, teorinya, “bilangan yang bisa di-bagi dengan bilangan prima pasti bukan bilangan prima” :)

      jadi punya lo ga usah terbatas range juga bisa, tapi pembaginya akan terus berkembang (naek terus) sesuai dengan bilangan2 prima yang ada sebelum angka yang mau dibagi.

      applicable juga ko’, gw pernah dapat code-nya waktu diskusiin maslaah blangan prima ama temen2.

  3. mo nanya nih? gmn dengan kasus mencari faktor sebuah bilangan berdigit 5… kalo ga bisa pake array, gmn dengan hash table? saya belum mengerti dengan penggunaan nya, share dong…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s