Apa itu bilangan prima?
Bilangan prima (en. Prime Number) adalah bilangan (angka) asli di mana lebih besar dari angka 1 dan tidak memiliki kelipatan (dari bilangan yang lebih kecil dibawahnya) sehingga bilangan prima hanya memiliki dua faktor pembagi yaitu bilangan itu sendiri dan angka satu, atau bisa dikatakan bilangan prima tidak akan habis dibagi (selalu ada angka dibelakang koma) dengan bilangan dibawahnya kecuali angka 1 dan bilangan prima tersebut.
 |
| Supaya teman-teman plengdut.com tidak bingung dengan apa penjelasan bilangan prima diatas, mari kita perinci lagi pengertian bilangan prima tersebut. |
Ciri dan Syarat Bilangan prima adalah:
- bilangan asli >1 (lebih besar dari 1), artinya angka 1 bukan bilangan prima,
- bilangan tanpa kelipatan dari bilangan-bilangan lebih kecil dibawahnya (artinya tidak punya kelipatan jika dibagi bilangan dibawahnya kecuali 1 dan bilangan prima sendiri),
- faktor pembagi bilangan prima hanya ada 2 yaitu bilangan 1 dan bilangan prima tersebut.
- jika bilangan prima dibagi selain 2 faktor angka yang telah di jelaskan pada point no.3, maka hasilnya tidak akan habis atau selalu ada angka di belakang koma (menjadi bilangan desimal).
Setelah memahami 4 point di atas, mari perhatikan contoh mencari bilangan prima berikut ini.
Contoh 1, apakah bilangan 8 merupakan bilangan prima?
Mari kita buktikan dengan cara sederhana yaitu membaginya menggunakan angka bilangan itu dan bilangan dibawahnya (8, 7, 6, 5, 4, 3, 2, 1), yaitu:
- 8:8=1
- 8:7=1,14
- 8:6=1,33
- 8:5=1,6
- 8:4=2
- 8:3=2,6
- 8:2=4
- 8:1=8
Perhatikan 8:8 serta 8:1 merupakan 2 faktor pembagi seperti yang sudah di terangkan pada syarat / ciri poin no.3 diatas di mana 8/8 dibagi bilangan prima itu sendiri, sedangkan 8/1 adalah dibagi 1. (terpenuhi)
Selanjutnya lihat 8/7, 8/6, 8/5, 8/3 kesemuanya menghasilkan koma. (terpenuhi)
Namun pada 8/4 dan 8/2 tidak menghasilkan koma atau habis terbagi (tidak terpenuhi syarat no.4)
8/4 hasilnya 2 atau bisa dibilang 8 merupakan kelipatan 4 (point.2 tidak terpenuhi)
8/2 hasil nya 4 atau 8 adalah kelipatan 2 (tidak terpenuhi point.2)
Sehingga 8 memiliki faktor pembagi (habis terbagi) oleh bilangan 8, 4, 2, 1, atau dikatakan juga ada 4 faktor pembagi (point. no 3 tidak terpenuhi, seharunya hanya ada dua bilangan yaitu bilangan prima itu sendiri dalam hal ini 8 dan angka 1)
Dari pembuktian tersebut, bisa ditarik kesimpulan bahwa 8 bukan bilangan prima karena memiliki kelipatan bilangan dari angka di bawahnya yaitu 2 dan 4, dan memiliki 4 faktor pembagi yang bisa habis terbagi.
Contoh 2, apakah 5 merupakan bilangan prima?
Kita buktikan lagi dengan cara yang sama seperti contoh 1. Bilangan lima pada soal dibagi bilangan 5, 4, 3, 2, 1, yaitu:
- 5:5=1
- 5:4=1,25
- 5:3=1,6
- 5:2=2,5
- 5:1=5
Amati, bilangan 5 hanya terbagi habis oleh 5 (bilangan prima itu sendiri) dan bilangan 1 atau bisa dibilang faktor pembagi cuma ada yaitu 5 dan 1 maka syarat prima no 3 terpenuhi.
Hasil 5:4, 5:3, dan 5:2 kesemuanya menghasilkan angka bilangan dibelakang koma (desimal) atau tidak habis terbagi (syarat prima no 4 terpenuhi), juga dapat dikatakan bahwa angka 5 tidak memiliki bilangan kelipatan dari angka dibawahnya kecuali 1 (syarat no 2 terpenuhi).
Kesimpulannya angka 5 adalah bilangan prima.
Filter Eratosthenes
Setelah memahami prinsip prinsip dasar mencari bilangan prima diatas, ada cara lain untuk mencari bilangan prima dalam angka-angka yang akan dicari. Prinsip tersebut adalah Filter Eratosthenes atau Saringan Eratosthenes.
Filter Eratosthenes adalah cara mencari bilangan prima mulai satu hingga n bilangan dengan membuat tabel saringan bilangan prima di mana teori ini diciptakan oleh Eratosthenes (276-194 SM) asal Alexandria. Pada dasarnya Filter Eratosthenes menyaring bilangan prima hingga n (n=batas angka yang akan dicari, mis. n=50 berarti yang akan dicari angka 1 hingga 50) dengan memanfaatkan tabel. Supaya sahabat plengdut.com tidak bingung, mari kita praktekan cara mencari bilangan prima dengan Filter Eratosthenes.
Contoh Filter Eratosthenes
Soal: Akan kita cari bilangan prima hingga n=20 atau 1 hingga 20, maka caranya:
Langkah membuat Filter Eratosthenes
- Buatlah tabel 2 kolom, pada kolom pertama (misal beri nama "cari") di isi angka-angka yang mau dicari bilangan primanya (dalam soal n=20), sedangkan kolom kedua beri nama "prima" biarkan kosong seperti berikut ini:
Cari (n = 20)
|
Prima
|
1
|
|
2
|
|
3
|
|
4
|
|
5
|
|
6
|
|
7
|
|
8
|
|
9
|
|
10
|
|
11
|
|
12
|
|
13
|
|
14
|
|
15
|
|
16
|
|
17
|
|
18
|
|
19
|
|
20
|
- Selanjutnya coret / tandai angka 1 di kolom pertama, dan tulis angka 2 di kolom "prima", seperti ini:
Cari (n = 20)
|
Prima
|
1
|
|
2
|
2
|
3
|
|
4
|
|
5
|
|
6
|
|
7
|
|
8
|
|
9
|
|
10
|
|
11
|
|
12
|
|
13
|
|
14
|
|
15
|
|
16
|
|
17
|
|
18
|
|
19
|
|
20
|
- Karena angka 2 sudah di kolom prima, maka angka 2 beserta kelipatannya (yaitu bilangan 2, 4, 6, 8, 10, 12, 14, 16, 18, 20) yang ada di kolom "cari" harus di filter dengan caea di coret/hapus/ditandai seperti berikut:
Cari (n = 20)
|
Prima
|
1
|
|
2
|
2
|
3
|
|
4
|
|
5
|
|
6
|
|
7
|
|
8
|
|
9
|
|
10
|
|
11
|
|
12
|
|
13
|
|
14
|
|
15
|
|
16
|
|
17
|
|
18
|
|
19
|
|
20
|
- Tersisa bilangan 3, 5, 7, 9, 11, 13, 15, 17, 19, dalam kolom cari, sedangkan bilangan yang sudah dicoret/ditandai tidak perlu dipindahkan ke kolom prima lagi.
- Lakukan cara yang sama untuk angka 3, yaitu pindahkan angka 3 ke kolom prima dan tandai/coret angka 3 beserta bilangan kelipatannya di kolom cari, sehingga menjadi:
Cari (n = 20)
|
Prima
|
1
|
|
2
|
2
|
3
|
3
|
4
|
|
5
|
|
6
|
|
7
|
|
8
|
|
9
|
|
10
|
|
11
|
|
12
|
|
13
|
|
14
|
|
15
|
|
16
|
|
17
|
|
18
|
|
19
|
|
20
|
- Ulangi kembali cara cara tadi untuk angka-angka selanjutnya, sehingga hasil akhirnya di dapat:
Cari (n = 20)
|
Prima
|
1
|
|
2
|
2
|
3
|
3
|
4
|
|
5
|
5
|
6
|
|
7
|
7
|
8
|
|
9
|
|
10
|
|
11
|
11
|
12
|
|
13
|
13
|
14
|
|
15
|
|
16
|
|
17
|
17
|
18
|
|
19
|
19
|
20
|
- Maka bilangan prima n=20 atau antara 1 hingga 20 yaitu 2, 3, 5, 7, 11, 13, 17, 19. Cukup mudah bukan cara mencari bilangan prima dengan Filter Eratosthenes? Silahkan kalian coba berlatih untuk mencari bilangan prima dengan rentang n yang lebih besar dari 20.
Selain metode Filter Eratosthenes untuk bilangan prima, ada juga metode saringan Filter Atkin yang ditemukan tahun 2004 untuk mencari bilangan prima. Namun Filter Atkin lebih rumit jika dihitung manual dibandingkan Filter Eratosthenes. Dengan menggunakan komputasi pemrograman komputer, saat ini sangat mudah mencari bilangan prima, bahkan bilangan prima sering dimanfaatkan untuk membentuk algoritma dalam dunia digital saat ini.