Penulis Topik: Bagaimana mencari bilangan prima? (Dibaca 65511 kali)

biobio · « **Jawab #30 pada:** Mei 07, 2009, 01:11:26 PM »

Kutip dari: Mtk Kerajaan Mataram pada Mei 06, 2009, 02:28:09 AM

yaitu sebenarnya kita tidak perlu ngecek semua pembagi dari 1 s.d. a, yakni cukup dengan 1 s.d. floor(sqrt(a)) <pembulatan ke bawah akar dari a>.

hmmm, ga ngerti gw... floor itu apa si?

insan sains · « **Jawab #31 pada:** Mei 07, 2009, 02:04:49 PM »

Kutip dari: biobio pada Mei 07, 2009, 01:11:26 PM

hmmm, ga ngerti gw... floor itu apa si?

Sudah disimpulkan :

Kutip dari: Mtk Kerajaan Mataram pada Mei 06, 2009, 02:28:09 AM

floor(sqrt(a)) <pembulatan ke bawah akar dari a>.

Jadi kalo kita punya angka 12.3 (dua belas koma tiga)
terus angka tersebut di-floor-kan maka hasilnya = 12

Jika :
x = 45.4
y=floor(x)
maka y = 45

CMIIW...!!

Mtk Kerajaan Mataram · « **Jawab #32 pada:** Mei 09, 2009, 05:29:28 AM »

Kutip dari: nash pada Mei 06, 2009, 05:43:36 AM

@mtk kerajaan mataram
mnurutku script tu ga efisien dan hasilny jga pasti lama...
ada ide lg?

Dari 1 s.d. floor(sqrt(a)), pilihlah hanya mengecek bilangan2 prima saja (jadi bilangan2 prima yang telah diperoleh diidentifikasi), ini akan sangat menghemat. Dan tentu saja inipun masih bukan untuk bilangan2 prima berdigit raksasa.

Firzal · « **Jawab #33 pada:** Mei 09, 2009, 06:11:39 AM »

Waaaaaa..........
bahasa pascal, q punya pengalaman buruk ma pascal,
tapi salut buat kerajaan mataram..........terus bersemangat mengembangkan matematika..........

insan sains · « **Jawab #34 pada:** Mei 12, 2009, 04:52:42 PM »

Dulu pernah nyobain pake bahasa C dengan menggunakan metoda Sieve of Eratosthenes. Prinsipnya adalah : mencari suatu bilangan yang hanya bisa dibagi oleh dirinya sendiri dan satu, kemudian mencoret dari daftar bilangan lain yang merupakan kelipatan bilangan prima yang ditemukan. Simple banget sih, tapi lumayanlah...

package percobaan;

public class Cariprima {

/**
* Program ini digunakan untuk mencari bilangan prima
* sebanyak yang diminta.
* Date : 18 Maret 2008 – Insan Sains
*/
public static void main(String[] args) {
/* jmlbilprima = Jumlah bilangan prima pertama yang akan dicari
* jmlketemu = jumlah bilangan prima yang saat ini ditemukan
* idx = bilangan yang saat ini sedang dicheck
* isprima = flag yang menunjukkan bahwa bilangan yang dicheck adalah bilangan prima
* prima[] = array yang merupakan kumpulan bilangan prima yang dicari.
*/
int jmlbilprima = 10000;
int jmlketemu = 0;
boolean isprima;
int prima[] = new int[jmlbilprima];

/*
* 1 bukan termasuk bilangan prima, jadi lewat saja
* Untuk memudahkan, bilangan prima yang pertama didefinisikan dulu
* Yaitu angka 2.
*/
int idx = 2;
prima[0] = 2;
/* Looping sampai ditemukan bilangan prima sejumlah yang diinginkan
*/
for (jmlketemu = 1; jmlketemu < jmlbilprima; jmlketemu++) {
isprima = false;
// Lakukan sampai ketemu bilangan prima berikutnya.
while (!isprima) {
// Lanjut ke bilangan yang akan diperiksa
idx++;
/* Bagi bilangan yang dicheck dengan bilangan prima yang sudah ketemu
* Periksa sisa baginya
* Bila salah satu hasil (sisa bagi) = kosong, berarti bukan prima
* Maka lanjut ke bilangan yagn dicheck berikutnya
* Bila SEMUA hasil (sisa bagi) = bersisa, berarti bilangan prima
* Maka masukkan bilangan ini sbg bilangan prima.
*/
for (int x = 0; x <= jmlketemu-1; x++) {
if ((idx % prima[ x ]) != 0) isprima = true;
else {
isprima = false;

break;
}
}
}
// Masukkan hasil bilangan prima yg ketemu ke look up table
prima[jmlketemu] = idx;
System.out.println(jmlketemu + “. “ + idx);
}

// Perlihatkan hasilnya dilayar
for (int x = 1; x <= jmlbilprima; x++) {
System.out.println(x + “. “ + prima[x-1]);
}
}
}

Sumber : Insan Sains Projects

nash · « **Jawab #35 pada:** Mei 12, 2009, 05:10:46 PM »

berhubung di kompie ku ga da compiler bhs C, ada yg mau bantu ngubah insan sains project di atas ke bhs vb?

Mtk Kerajaan Mataram · « **Jawab #36 pada:** Mei 16, 2009, 11:57:29 AM »

@insan sains
Ini program mendaftar bilangan prima yaa?
Saya kok masih gamang dengan maksud dari :

for (int x = 0; x <= jmlketemu-1; x++)
{if ((idx % prima[ x ]) != 0) isprima = true;
else {isprima = false;break;}}

<'if; tsb di dalam 'for', jadi pengujian ikut berulang (bisa berganti-ganti hasil isprima-nya selama itu >, kok mulai dari 0 yaa pembaginya?

insan sains · « **Jawab #37 pada:** Mei 16, 2009, 04:12:13 PM »

@Mtk Kerajaan Mataram

Ya.. program yang saya bikin untuk mendaftar bilangan prima.

Jadi kalo di program tersebut diisikan

int jmlbilprima = 10000;

Maka komputer akan mendaftar dan menampilkan bilangan prima pertama hingga ke 10 ribu. Jadi kalo mau mendaftar dan menampilkan bilangan prima pertama hingga ke 1 juta. Tinggal mengganti jmlbilprima saja.

Saya kutipkan lagi blok program yang ditanyakan :

Kutip dari: insan sains pada Mei 12, 2009, 04:52:42 PM

for (int x = 0; x <= jmlketemu-1; x++) {
   if ((idx % prima[ x ]) != 0) isprima = true;
   else {
   isprima = false;

   break;
   }
}

Script program diatas untuk melakukan pengujian terhadap bilangan yang sedang diperiksa.

Sebelumnya perlu diketahui bahwa bilangan prima yang telah diuji akan dimasukkan pada sebuah array yang bernama prima[]. Yang sebelumnya telah disediakan bahwa array itu akan sebanyak jumlah bilangan prima yang dimasukkan.

int prima[] = new int[jmlbilprima];

Misal kita telah mendapatkan 9999 bilangan prima. Maka bilangan prima yang ke 10.000 tidak harus diuji dari angka awal lagi, melainkan mengujinya dengan 9999 bilangan prima yang sudah ditemukan. Sebagaimana metode Sieve of Eratosthenes : "Mencari suatu bilangan yang hanya bisa dibagi oleh dirinya sendiri dan satu, kemudian mencoret dari daftar bilangan lain yang merupakan kelipatan bilangan prima yang ditemukan"

for (int x = 0; x <= jmlketemu-1; x++) {

Nah 0 yang dimaksud, dalam script program diatas bukan melakukan pengujian dengan 0. Melainkan melakukan pengujian dengan bilangan prima yang telah ditemukan yang berada pada array ke-0 (array pertama, dalam hal ini program sudah langsung mendefinisi bahwa bilangan prima pada array ke-0 adalah angka 2)

prima[0] = 2;

Pengujian itu sendiri dilakukan pada script berikut :

if ((idx % prima[ x ]) != 0) isprima = true;

Si idx itu sendiri akan terus bertambah, sampai bilangan prima yang ke sekian (sbgmn yang diinginkan pada jmlbilprima) sudah ditemukan.

Mtk Kerajaan Mataram · « **Jawab #38 pada:** Mei 16, 2009, 04:39:04 PM »

Okay trims,
maksudnya anu yaa, jika idx sampai ke bilangan prima, maka akan diperoleh :
isprima=true
isprima=true
isprima=true
.....
isprima=true
sampai x = jmlketemu-1
lalu ganti idx.

Dan jika idx bukan bilangan prima maka
isprima=true
isprima=true
isprima=true
.....
isprima=false
break
lalu ganti idx.

insan sains · « **Jawab #39 pada:** Mei 16, 2009, 05:26:23 PM »

Kutip dari: Mtk Kerajaan Mataram pada Mei 16, 2009, 04:39:04 PM

Okay trims,
maksudnya anu yaa,

Untung ada lanjutannya.... kekekeke

Yups tepat sekali

Btw.. saya pengen nyari pake metode lain yang lebih cepet. Bisa di definisikan gak formulanya? Thanks

Nabih · « **Jawab #40 pada:** Mei 24, 2009, 07:20:27 PM »

Jadi Inget kuliah sejarah Matematika

aku juga mau jawab pake sievve de erastostenes (kayaknya salah deh ejaanya)

Tapi udah dijawab ama wildan

cara itu udah masuk ke MATLAB 7.2 (maungkin versi sebelumanya ada)

caranya ketik prome(1000000000)

terserah bilangan berapapun ntar akan muncul semua bilangn prima yang kurang dari bil yang kamu mau, proses kurang dari 4 menit asalakan tidak lebih dari 16juta digit, tergantung RAM juga dinx

Alicha · « **Jawab #41 pada:** Mei 24, 2009, 07:54:39 PM »

Himpunan bilangan asli
Himpunan bilangan asli adalah himpunan bilangan yang anggota-anggotanya merupakan bilangan bulat positif.

N = {1,2,3,4,5,6,......}

Himpunan bilangan prima
Himpunan bilangan prima adalah himpunan bilangan-bilangan asli yang hanya dapat dibagi dirinya sendiri dan satu, kecuali angka 1.

P = {2,3,5,7,11,13,....}

Himpunan bilangan cacah
Himpunan bilangan cacah adalah himpunan bilangan yang anggota-anggotanya merupakan bilangan bulat positif digabung dengan nol.

C = {0,1,2,3,4,5,6,....}

Himpunan bilangan bulat
Himpunan bilangan bulat adalah himpunan bilangan yang anggota-anggotanya seluruh bilangan bulat, baik negatif, nol, dan positif.

B = {...,-3,-2,-1,0,1,2,3,...}

Himpunan bilangan rasional
Himpunan bilangan rasional adalah himpunan bilangan yang anggota-anggonya merupakan bilangan yang dapat dinyatakan sebagai:
p/q dimana p,q Î bulat dan q ¹ 0 atau dapat dinyatakan sebagai suatu desimal berulang.

contoh: 0,-2, 2/7, 5, 2/11, dan lain lain

Himpunan bilangan irasional
Himpunan bilangan irasional adalah himpunan bilangan yang anggota-anggotanya tidak dapat dinyatakan sebagai sebagai p/q atau tidak dapat dinyatakan sebagai suatu desimal berulang.

contoh: log 2, e, Ö7

Himpunan bilangan riil
Himpunan bilangan riil adalah himpunan yang anggota-anggotanya merupakan gabungan dari himpunan bilangan rasional dan irasional.

contoh: log 10, 5/8, -3, 0, 3

Himpunan bilangan imajiner
Himpunan bilangan imajiner adalah himpunan bilangan yang anggota-anggotanya merupakan i (satuan imajiner) dimana i merupakan lambang bilangan baru yang bersifat i² = -1

contoh: i, 4i, 5i

Himpunan bilangan kompleks
Himpunan bilangan kompleks adalah himpunan bilangan yang anggota-anggotanya (a + bi) dimana a, b Î R, i² = -1, dengan a bagian riil dan b bagian imajiner.

contoh: 2-3i, 8+2

Mtk Kerajaan Mataram · « **Jawab #42 pada:** Mei 24, 2009, 09:25:23 PM »

Yuk kembali ke topik, kalau dalam topik "probable prime", kita pertama membahas a_PRP untuk menguji primalitas berdasar teorema fermat dengan keterbatasannya.
Ini ada yang namanya Strong Probable Prime, yang juga menguji primalitas secara lebih kuat, dalam kesendirian memang masih belum bisa menyeluruh, tapi kalau digabung, misalnya suatu bilangan kurang dari 2.000.0000 dan termasuk 2_SPRP dan 3_SPRP, maka bilangan itu prima, dan masih banyak contoh lain.

Ujinya adalah sebagai berikut, jika suatu bilangan berbentuk $n = d \cdot 2^s + 1$ , dimana $d$ ganjil. Bilangan $n$ merupakan $a$ SPRP jika memenuhi salah satu berikut :
(i) $a^d \equiv 1 mod n$

(ii) $a^{d\cdot 2^r} \equiv -1 mod n \quad \mbox{ untuk }0\leq r\leq(s-1)$

Contoh :
(1) 7 termasuk 2_SPRP, karena $7=3 \cdot 2^1+1$
$a=2, d=3, s=1$
dan $2^3 \equiv 1 mod 7$

(2) 15 tidak termasuk 2_SPRP karena $15=7 \cdot 2^1+1$
$a=2, d=7, s=1$
(i) $2^7 =128$ tidak berbentuk $1 mod 15$
(ii) karena s=1, maka r hanya 0 saja, dan
$2^{7\cdot 2^0} = 128$ juga tidak berbentuk $-1 mod 15$ ,
Karena tidak memenuhi kedua-dua kriteria maka 15 bukan 2_SPRP.

Code program untuk tidak diobral, biasanya terdapat di jurnal matematika, saya berencana untuk membuatnya. Sedangkan bukti untuk uji ini nanti kita coba di thread 'prpbable prime' : http://www.forumsains.com/matematika/probable-prime/

Nabih · « **Jawab #43 pada:** Mei 24, 2009, 09:49:44 PM »

sprp itu apa???

Mtk Kerajaan Mataram · « **Jawab #44 pada:** Mei 25, 2009, 07:03:19 AM »

@Nabih
Silahkan baca pertama kali ceritanya di http://www.forumsains.com/matematika/probable-prime/

Artikel Sains

Aku Cinta ForSa

Pranala Luar

ShoutBox!

Penulis Topik: Bagaimana mencari bilangan prima? (Dibaca 65511 kali)