Bilangan prima

132 bahasa

• Halaman
• Pembicaraan

• Baca
• Sunting
• Sunting sumber
• Lihat riwayat

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas

Bilangan komposit dapat disusun menjadi persegi panjang, sedangkan bilangan prima tidak dapat.

Bilangan prima adalah bilangan asli lebih dari 1 yang bukan hasilkali dari dua bilangan asli yang lebih kecil. Bilangan asli yang lebih dari 1 dan bukan bilangan prima disebut bilangan komposit. Misalnya, 5 adalah bilangan prima karena 5 dapat ditulis sebagai ${\displaystyle 1\times 5}$ atau ${\displaystyle 5\times 1}$, sedangkan 4 bukanlah bilangan prima karena hasilkalinya (${\displaystyle 2\times 2}$), dimana kedua bilangan lebih kecil dari 4. Bilangan prima merupakan bagian pusat dari teori bilangan karena melibatkan teorema dasar aritmetika: setiap bilangan asli lebih besar dari 1 adalah bilangan prima itu sendiri atau dapat difaktorkan sebagai hasil kali tunggal hingga urutannya.

Sifat-sifat yang menjadikan bilangan prima disebut primalitas. Metode sederhana namun lambat yang memeriksa primalitas untuk bilangan ${\displaystyle n}$, disebut pembagian percobaan. Metode ini menguji apakah ${\displaystyle n}$ kelipatan dari suatu bilangan bulat antara ${\displaystyle 2}$ dan ${\displaystyle {\sqrt {n}}}$. Algoritma lebih cepatnya adalah uji primalitas Miller–Rabin, algoritma cepat namun memiliki kesempatan galat kecil; dan uji primalitas Agrawal–Kayal–Saxena, algoritma yang selalu memberikan solusi yang benar dalam waktu polinomial, namun sangat lambat bila dipraktekkan. Metode cepat khususnya tersedia dalam bilangan bentuk khusus, seperti bilangan Mersenne. Hingga pada Desember 2018, bilangan prima terbesar yang diketahui merupakan bilangan prima Mersenne dengan 24.862.048 digit.^[1]

Sekitar 300 SM, Euklides menjel