Memahami hasil
Tabel di bawah menunjukkan ketiga output untuk contoh input.
| Input | Prima? | Faktorisasi | Prima berikutnya |
|---|---|---|---|
| 97 | Ya | 97 | 101 |
| 84 | Tidak | 2 x 2 x 3 x 7 | 89 |
| 100 | Tidak | 2 x 2 x 5 x 5 | 101 |
| 2 | Ya (satu-satunya prima genap) | 2 | 3 |
| 1 | Tidak (bukan prima maupun komposit) | - | 2 |
- Angka 1 bukan bilangan prima: bilangan prima harus memiliki tepat dua pembagi berbeda, dan 1 hanya memiliki satu. Mengecualikan 1 menjaga keunikan faktorisasi prima.
- Pembagian percobaan bersifat eksak tetapi melambat untuk input yang sangat besar; kalkulator ini menerima angka hingga 10^12, dengan pencarian yang menguji pembagi hingga satu juta.
- Pencarian prima berikutnya dijamin berakhir dengan cepat pada rentang ini: menurut postulat Bertrand, selalu ada bilangan prima di antara n dan 2n.
Apa itu bilangan prima?
Bilangan prima adalah bilangan asli lebih besar dari 1 yang memiliki tepat dua pembagi positif: 1 dan dirinya sendiri. Bilangan prima pertama adalah 2, 3, 5, 7, 11, 13, 17, 19, 23 dan 29. Angka 2 adalah satu-satunya bilangan prima genap, karena setiap bilangan genap lainnya habis dibagi 2. Bilangan lebih besar dari 1 yang bukan prima disebut komposit; angka 1 bukan prima maupun komposit, menurut definisinya.
Teorema dasar aritmetika menyatakan bahwa setiap bilangan bulat lebih besar dari 1 dapat ditulis sebagai hasil kali bilangan prima dengan tepat satu cara, terlepas dari urutan faktornya. Faktorisasi prima yang unik ini adalah alasan mengapa bilangan prima disebut sebagai blok pembangun bilangan bulat: 84 = 2^2 x 3 x 7, dan tidak ada kombinasi bilangan prima lain yang hasil kalinya 84.
Bilangan prima jumlahnya tak terhingga — hasil yang dibuktikan oleh Euclid sekitar 300 SM — dan menjadi semakin jarang seiring bertambahnya angka, meskipun tanpa pola sederhana. Bilangan prima besar mendasari kriptografi kunci publik modern (seperti RSA), yang bergantung pada kesulitan praktis dalam memfaktorkan hasil kali dua bilangan prima yang sangat besar.
Cara menggunakan kalkulator bilangan prima ini
- Masukkan bilangan bulat n minimal 1. Desimal dibulatkan ke bawah ke bilangan bulat terdekat.
- Baca hasil uji keprimaan: tanda centang berarti angka tersebut prima, tanda silang berarti komposit (atau 1, yang bukan keduanya).
- Baca faktorisasi prima — hasil kali unik bilangan prima yang sama dengan angka Anda. Untuk input prima, faktorisasinya adalah angka itu sendiri.
- Baca bilangan prima berikutnya, yaitu bilangan prima terkecil yang lebih besar dari angka Anda.
Cara pengujian keprimaan: pembagian percobaan
Bilangan n adalah komposit jika dan hanya jika ia memiliki pembagi lebih besar dari 1 dan paling banyak akar kuadrat dari n. Ini karena pembagi berpasangan: jika n = a x b dengan a <= b, maka a <= sqrt(n). Karena itu, pembagian percobaan hanya perlu menguji calon pembagi hingga sqrt(n) — setelah memeriksa 2, hanya kandidat ganjil yang diperlukan.
Contoh perhitungan (prima): n = 97. Akar kuadrat dari 97 adalah sekitar 9,85, sehingga cukup menguji 2, 3, 5, 7 dan 9. 97 adalah ganjil; 9 + 7 = 16 tidak habis dibagi 3; tidak berakhiran 0 atau 5; 97 / 7 = 13,857...; dan 97 / 9 bukan bilangan bulat. Tidak ada pembagi yang ditemukan, sehingga 97 adalah prima.
Contoh perhitungan (faktorisasi): n = 84. Bagi habis dengan bilangan prima dari yang terkecil: 84 / 2 = 42, 42 / 2 = 21, 21 / 3 = 7, dan 7 adalah prima. Jadi 84 = 2 x 2 x 3 x 7 = 2^2 x 3 x 7. Bilangan prima berikutnya setelah 84 adalah 89 (85 = 5 x 17, 86 = 2 x 43, 87 = 3 x 29, 88 = 2^3 x 11).
Kesalahan umum
- Menganggap 1 sebagai bilangan prima — menurut definisi, bilangan prima memiliki tepat dua pembagi berbeda, dan 1 hanya memiliki satu.
- Mengasumsikan semua bilangan prima ganjil: 2 adalah prima, dan merupakan satu-satunya prima genap.
- Menguji pembagi hingga n, bukan berhenti di sqrt(n) — setiap bilangan komposit memiliki faktor pada atau di bawah akar kuadratnya.
- Meyakini semua bilangan ganjil adalah prima: 9 = 3 x 3, 15 = 3 x 5 dan 21 = 3 x 7 adalah komposit ganjil.
- Mengacaukan faktorisasi prima dengan faktorisasi apa pun: 84 = 4 x 21 adalah sebuah faktorisasi, tetapi faktorisasi primanya adalah 2 x 2 x 3 x 7.
Pertanyaan yang sering diajukan
Bagaimana cara memeriksa apakah suatu angka adalah prima?
Uji apakah ada bilangan bulat dari 2 hingga akar kuadrat dari angka tersebut yang membaginya habis. Jika tidak ada, angka tersebut prima. Untuk 97, akar kuadratnya sekitar 9,85, dan tidak satu pun dari 2, 3, 5, 7 atau 9 yang membagi 97, sehingga 97 adalah prima. Pasangan pembagi menjamin bahwa setiap bilangan komposit memiliki faktor pada atau di bawah akar kuadratnya.
Mengapa 1 bukan bilangan prima?
Bilangan prima didefinisikan sebagai memiliki tepat dua pembagi positif berbeda, 1 dan dirinya sendiri; angka 1 hanya memiliki satu pembagi. Definisi ini juga melindungi teorema dasar aritmetika: jika 1 dianggap prima, faktorisasi tidak lagi unik (6 = 2 x 3 = 1 x 2 x 3 = 1 x 1 x 2 x 3, dan seterusnya).
Apa itu faktorisasi prima?
Ini adalah penguraian suatu angka sebagai hasil kali bilangan prima, yang dijamin unik oleh teorema dasar aritmetika terlepas dari urutannya. Misalnya, 84 = 2 x 2 x 3 x 7. Untuk menemukannya, bagi berulang kali dengan bilangan prima terkecil yang habis membaginya hingga hasil bagi yang tersisa adalah 1 atau prima.
Apakah 2 adalah bilangan prima?
Ya — 2 adalah prima karena pembaginya hanya 1 dan 2, dan merupakan satu-satunya prima genap. Setiap bilangan genap lainnya habis dibagi 2 sehingga komposit. Inilah sebabnya uji keprimaan menangani 2 secara terpisah lalu hanya memeriksa kandidat ganjil.
Ada berapa banyak bilangan prima?
Jumlahnya tak terhingga, sebagaimana dibuktikan Euclid sekitar 300 SM: diberikan daftar prima terbatas mana pun, angka yang terbentuk dari perkalian semuanya ditambah 1 tidak habis dibagi oleh satu pun dari mereka, sehingga ada prima yang hilang dari daftar tersebut. Bilangan prima semakin jarang seiring bertambahnya angka — menurut teorema bilangan prima, kepadatan prima di sekitar n kira-kira 1 / ln(n) — tetapi tidak pernah berhenti.
Mengapa bilangan prima penting dalam kriptografi?
Sistem kunci publik seperti RSA bertumpu pada suatu asimetri: mengalikan dua bilangan prima besar itu mudah, tetapi menemukan kembali bilangan prima tersebut dari hasil kalinya sangat sulit secara komputasi pada ukuran yang digunakan dalam praktik (ratusan digit). Kunci keamanan dibangun dari hasil kali semacam itu, sehingga pembuatan bilangan prima dan pengujian keprimaan menjadi operasi kriptografi inti.
Referensi
- Weisstein, Eric W. "Prime Number" and "Fundamental Theorem of Arithmetic." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. Oxford University Press (primes, unique factorization, Bertrand's postulate).
- Euclid. Elements, Book IX, Proposition 20 (infinitude of primes).