Pemeriksa Bilangan Prima

Bilangan prima memiliki tepat dua pembagi: 1 dan dirinya sendiri.

Bilangan prima yang pertama adalah 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

Bilangan prima adalah blok penyusun dari semua bilangan bulat.

Setiap bilangan bulat > 1 dapat dinyatakan secara unik sebagai perkalian bilangan prima.

Contohnya, 60 = 2² × 3 × 5.

Huruf atau konsep ini sangat fundamental dalam matematika dan kriptografi.

Untuk memeriksa apakah angka n adalah bilangan prima, ujilah apakah ada bilangan bulat antara 2 dan akar kuadrat dari n yang membaginya habis; jika tidak ada, maka n adalah bilangan prima.

Pertama-tama, tangani kasus-kasus kecil:

• angka di bawah 2 bukan bilangan prima
• 2 dan 3 adalah bilangan prima
• angka genap apa pun di atas 2 adalah bilangan komposit

Kemudian, ujilah pembagi ganjil hingga √n, karena pembagi selalu berpasangan dengan anggota yang lebih kecil tidak boleh melebihi akar kuadrat.

Sebagai contoh, memeriksa 97 hanya memerlukan pengujian 3, 5, dan 7 (karena √97 ≈ 9,85), dan tidak ada yang membaginya, jadi 97 adalah bilangan prima. Wolfram MathWorld mendefinisikan hal ini sebagai pembagian uji coba, yaitu uji kerimaan yang paling langsung.

Metode akar kuadrat berarti Anda hanya perlu menguji calon pembagi hingga √n alih-alih sampai ke n.

Alasannya adalah jika n = a × b, maka setidaknya salah satu faktor a atau b harus kurang dari atau sama dengan √n; jika tidak, hasil kali keduanya akan melebihi n. Jadi, jika tidak ada faktor yang ditemukan di bawah √n, tidak ada pula faktor yang lebih besar.

Hal ini secara drastis mengurangi pekerjaan: memeriksa apakah 9.973 adalah bilangan prima hanya memerlukan pengujian pembagi hingga sekitar 99, bukan hampir 10.000.

Khan Academy menggunakan argumen pasangan ini untuk menjelaskan mengapa pembagian uji coba berhenti pada akar kuadrat, sehingga pemeriksaan kerimaan secara manual menjadi praktis.

Saringan Eratosthenes menemukan semua bilangan prima hingga batas N dengan menandai kelipatan dari setiap bilangan prima secara berulang sebagai bilangan komposit.

Mulailah dengan daftar bilangan bulat dari 2 hingga N. Ambil 2, tandai 4, 6, 8, ... sebagai komposit; pindah ke angka berikutnya yang tidak ditandai, yaitu 3, dan tandai 6, 9, 12, ...; lanjutkan dengan 5, 7, dan seterusnya. Angka-angka yang tetap tidak ditandai adalah bilangan prima.

Jika diterapkan hingga 30, saringan ini menyisakan 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Dinamakan dari matematikawan Yunani Eratosthenes dari Kirene, algoritma ini (yang didokumentasikan oleh Encyclopaedia Britannica) adalah salah satu cara tertua dan paling efisien untuk mencantumkan bilangan prima dalam suatu rentang.

Teorema Dasar Aritmatika menyatakan bahwa setiap bilangan bulat yang lebih besar dari 1 adalah bilangan prima atau dapat ditulis sebagai perkalian dari bilangan-bilangan prima dengan tepat satu cara, terlepas dari urutan faktor-faktornya.

Sebagai contoh, 360 = 2³ × 3² × 5, dan tidak ada kombinasi bilangan prima lain yang menghasilkan 360 jika dikalikan. Keunikan inilah yang membuat bilangan prima disebut sebagai blok bangunan dari bilangan bulat.

Menurut Wolfram MathWorld, teorema ini mendasari faktorisasi prima, perhitungan pembagi persekutuan terbesar, dan aritmatika modular.

Kalkulator kami menggunakannya saat memfaktorkan suatu angka, menjamin bahwa dekomposisi prima yang dihasilkannya adalah satu-satunya yang mungkin.

Bilangan prima kembar adalah pasangan bilangan prima yang selisihnya tepat 2, seperti (3, 5), (5, 7), (11, 13), (17, 19), dan (29, 31).

Kesenjangan antara bilangan prima berturut-turut umumnya semakin besar seiring dengan membesarnya angka, meskipun bilangan prima kembar terus bermunculan. Apakah ada tak terhingga jumlah bilangan prima kembar adalah Konjektur Bilangan Prima Kembar yang terkenal, yang masih belum terbukti.

Ensiklopedia Daring Urutan Bilangan Bulat (OEIS) mengkatalogkan anggota bawah dari pasangan bilangan prima kembar dalam urutan A001359.

Memahami kesenjangan prima membantu menjelaskan mengapa bilangan prima menjadi lebih jarang: di dekat satu juta, jarak antar bilangan prima rata-rata sekitar 14, sebuah tren yang dijelaskan oleh Teorema Bilangan Prima dalam Perpustakaan Digital Fungsi Matematika NIST.

Bilangan prima mendukung kriptografi modern, terutama enkripsi RSA, yang mengamankan perbankan online, situs web HTTPS, dan tanda tangan digital. RSA bergantung pada fakta bahwa mengalikan dua bilangan prima besar adalah hal yang mudah, tetapi memfaktorkan kembali hasil kali tersebut menjadi bilangan-bilangan prima asalnya merupakan hal yang sangat sulit secara komputasi.

Selain keamanan, bilangan prima muncul dalam:

• penentuan ukuran tabel hash (tabel dengan panjang prima mengurangi kolaborasi)
• pembuatan angka pseudo-acak
• kode koreksi kesalahan
• siklus hidup jangkrik yang berevolusi di sekitar tahun berangka prima untuk menghindari pemangsa

Britannica mencatat bahwa faktorisasi prima juga menyederhanakan pecahan dan menghitung kelipatan persekutuan terkecil. Kalkulator ini mendukung tugas-tugas tersebut dengan memfaktorkan angka dan menghasilkan bilangan prima untuk perancangan algoritma maupun pekerjaan rumah matematika.

Sebuah bilangan prima memiliki tepat dua pembagi positif yang berbeda, yaitu 1 dan dirinya sendiri, sementara bilangan komposit memiliki lebih dari dua pembagi.

Sebagai contoh, 13 adalah bilangan prima (pembaginya 1 dan 13), dan 12 adalah bilangan komposit (pembaginya 1, 2, 3, 4, 6, 12). Angka 1 bukan merupakan bilangan prima maupun komposit, karena ia hanya memiliki satu pembagi.

Konvensi ini menjaga Teorema Dasar Aritmatika tetap rapi: jika 1 dihitung sebagai bilangan prima, faktorisasi tidak akan lagi unik karena Anda dapat menyisipkan angka 1 berapa pun.

Encyclopaedia Britannica dan Khan Academy sama-sama menekankan perbedaan ini, itulah sebabnya alat kami memberi label pada 1 secara terpisah dari bilangan prima dan komposit.

Bilangan prima Mersenne adalah bilangan prima dalam bentuk 2^p − 1, di mana eksponen p itu sendiri adalah bilangan prima; contohnya meliputi 3 (2² − 1), 7 (2³ − 1), 31 (2⁵ − 1), dan 127 (2⁷ − 1).

Namun, tidak setiap eksponen prima menghasilkan bilangan prima: 2¹¹ − 1 = 2047 = 23 × 89 adalah bilangan komposit.

Bilangan prima Mersenne penting karena uji cepat yang disebut uji Lucas-Lehmer membuat mereka lebih mudah diverifikasi daripada angka sembarang, sehingga bilangan prima terbesar yang diketahui hampir selalu merupakan bilangan prima Mersenne dengan puluhan juta digit.

Pencarian Bilangan Prima Mersenne Internet Besar (GIMPS) mengoordinasikan para sukarelawan untuk menemukannya. Urutan OEIS A000668 mencantumkan bilangan prima Mersenne yang sudah diketahui.

• Kesalahan paling umum adalah memperlakukan 1 sebagai bilangan prima; padahal bukan, karena bilangan prima harus memiliki tepat dua pembagi.
• Kesalahan lainnya adalah lupa bahwa 2 adalah satu-satunya bilangan prima genap, sehingga orang-orang keliru melewatkannya atau salah berasumsi bahwa angka genap lainnya mungkin merupakan bilangan prima.
• Kesalahan ketiga adalah menghentikan pembagian uji coba terlalu cepat atau terlalu lambat: Anda harus menguji semua pembagi hingga √n, bukan hanya beberapa pembagi kecil saja.
• Orang-orang juga sering mencampuradukkan faktorisasi prima dengan mencantumkan semua faktor; 12 memiliki faktor 1, 2, 3, 4, 6, 12 tetapi faktorisasi primanya hanyalah 2² × 3.
• Terakhir, berasumsi bahwa setiap angka dalam bentuk 6k ± 1 adalah bilangan prima adalah keliru; 25 = 6(4) + 1 adalah bilangan komposit.