Pemeriksa Bilangan Prima
Periksa apakah suatu bilangan adalah prima dan temukan faktor-faktornya. Gunakan pemeriksa prima gratis ini untuk menguji bilangan apa pun secara instan. Tanpa daftar.
Apakah Angka Prima?
Angka prima adalah bilangan alami yang lebih besar dari 1 yang memiliki dua faktor unik: 1 dan dirinya sendiri. Angka prima pertama adalah: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97...
Fakta penting tentang angka prima:
- 2 adalah satu-satunya angka prima genap. Setiap bilangan genap lainnya dapat dibagi oleh 2, sehingga memiliki lebih dari dua faktor.
- 1 bukanlah angka prima menurut konvensi modern. Menghilangkan 1 mempertahankan keunikan faktorisasi prima (Teorema Dasar Arithmetika).
- Angka prima tak terhingga. Euclid membuktikan hal ini sekitar 300 SM: asumsikan daftar angka prima yang terbatas p₁, p₂, ..., pₙ. Kemudian bilangan (p₁ × p₂ × ... × pₙ) + 1 adalah prima atau memiliki faktor prima yang tidak ada dalam daftar — kontradiksi. Oleh karena itu, daftar adalah tak terhingga.
- Seiring angka semakin besar, angka prima semakin jarang — tetapi mereka tidak pernah berhenti. Ada 25 angka prima di bawah 100, 168 di bawah 1.000, dan 78.498 di bawah 1.000.000.
Bilangan komposit adalah bilangan positif yang lebih besar dari 1 yang bukan prima — memiliki setidaknya satu faktor lain selain 1 dan dirinya sendiri. Bilangan 12 adalah komposit karena 12 = 2 × 6 = 3 × 4 = 2 × 2 × 3. Setiap bilangan komposit memiliki faktorisasi prima unik (Teorema Dasar Arithmetika).
Cara Cek Jika Angka adalah Prima
Ada beberapa metode untuk tes prima, mulai dari pembagian percobaan sederhana hingga algoritma probabilistik canggih:
Pembagian Percobaan (metode dasar): Tes apakah bilangan bulat mana pun dari 2 hingga √n dapat membagi n secara rata. Jika tidak ada, maka n adalah prima. Anda hanya perlu memeriksa hingga √n karena jika n = a × b dengan a ≤ b, maka a ≤ √n. Jika tidak ada pembagi yang ditemukan hingga √n, maka tidak ada pembagi di atas √n juga.
Pembagian Percobaan Optimal: Setelah memeriksa pembagian oleh 2, hanya tes bilangan ganjil. Selanjutnya: cek 2, 3, kemudian hanya bilangan dalam bentuk 6k±1 (sejak semua prima > 3 memiliki bentuk ini). Ini mengurangi jumlah tes sekitar 66% dibandingkan dengan pembagian percobaan sederhana.
| Bilangan | √n (aprx) | Test pembagi hingga | Prima? |
|---|---|---|---|
| 97 | 9,85 | 2, 3, 5, 7 | Ya (tidak ada yang dapat membagi secara rata) |
| 91 | 9,54 | 2, 3, 5, 7 | Tidak (7 × 13 = 91) |
| 1.009 | 31,76 | Up to 31 | Ya (prima) |
| 1.001 | 31,64 | Up to 31 | Tidak (7 × 11 × 13 = 1.001) |
| 7.919 | 88,99 | Up to 89 | Ya (prima ke-1.000) |
Untuk bilangan besar (ratusan digit), pembagian percobaan tidak dapat dilakukan secara komputasional. Tes canggih seperti tes prima Miller-Rabin (probabilistik, digunakan dalam kriptografi) dan tes prima AKS (deterministik polynomial-time, 2002) digunakan alih-alih.
Perpecahan Prima
Setiap bilangan komposit dapat ditulis sebagai produk unik dari prima — perpecahan prima. Ini dijamin oleh Teorema Fundamental dari Arithmetika. Untuk menemukan perpecahan prima, bagi secara berulang dengan faktor prima terkecil:
| Bilangan | Perpecahan prima | Pemecahan faktor |
|---|---|---|
| 12 | 2² × 3 | 12 → 4×3 → 2×2×3 |
| 60 | 2² × 3 × 5 | 60 → 4×15 → 2²×3×5 |
| 100 | 2² × 5² | 100 → 4×25 → 2²×5² |
| 360 | 2³ × 3² × 5 | 360 → 8×45 → 2³×3²×5 |
| 1,024 | 2¹⁰ | Semua faktor prima adalah 2 |
| 2,310 | 2 × 3 × 5 × 7 × 11 | Produk dari 5 prima pertama |
Perpecahan prima digunakan untuk menemukan pembilang umum terbesar (GCD) dan pembilang umum terkecil (LCM) dari bilangan. GCD(12, 18) = 2² × 3? Tidak — ambil kuasa minimum dari prima yang sama: GCD = 2¹ × 3¹ = 6. LCM mengambil kuasa maksimum: LCM(12, 18) = 2² × 3² = 36.
Mengapa Prima Penting: Aplikasi dalam Matematika dan Teknologi
Prima adalah "atom" dari aritmatika — Teorema Fundamental dari Arithmetika menyatakan bahwa setiap bilangan positif lebih besar dari 1 adalah prima atau dapat ditulis sebagai produk unik dari prima. Uniknya membuat prima sebagai blok bangunan yang tidak dapat dipecahkan dari semua bilangan.
Keamanan internet modern bergantung pada bilangan prima. Enkripsi RSA (digunakan untuk HTTPS, enkripsi email, dan tandatangan digital) menghasilkan kunci publik dengan mengalikan dua bilangan prima besar p dan q untuk membentuk n = p × q. Kunci enkripsi dan dekripsi dihitung menggunakan aritmatika modulernya dengan n. Keamanan bergantung pada masalah pemecahan faktor integer: diberikan n (sebuah bilangan 2048-bit dengan ~617 digit desimal), menemukan p dan q adalah tidak mungkin dengan teknologi saat ini.
Perjanjian kunci Diffie-Hellman menggunakan modulus prima besar untuk kesepakatan kunci yang aman. Ketika Anda terhubung ke situs web melalui HTTPS, bilangan prima melindungi data Anda secara diam-diam dalam waktu nyata.
Tabel hash menggunakan array ukuran prima untuk mengurangi tabrakan. Ketika fungsi hash menerjemahkan kunci ke indeks bucket, menggunakan bilangan prima dari bucket memastikan distribusi yang lebih baik karena prima tidak memiliki faktor yang dapat menciptakan pola tabrakan sistematis.
Generator bilangan acak palsu (PRNG) menggunakan modulus prima dalam generator kongruens linear dan algoritma lainnya. Periode (sebelum ulang) dari generator seperti itu sering kali sama dengan modulus prima minus 1.
Jenis-Jenis Prima Khusus
Di dalam setiap prima yang tak terhingga, beberapa subset memiliki sifat atau signifikansi khusus:
| Jenis | Definisi | Contoh |
|---|---|---|
| Prima kembar | Prima yang berbeda oleh 2 | (3,5), (11,13), (17,19), (41,43) |
| Prima Mersenne | Prima dalam bentuk 2ⁿ − 1 | 3, 7, 31, 127, 8,191 |
| Prima Fermat | Prima dalam bentuk 2^(2ⁿ) + 1 | 3, 5, 17, 257, 65,537 |
| Prima Sophie Germain | p dan 2p+1 adalah prima | 2, 3, 5, 11, 23, 29 |
| Prima palindromik | Prima yang membaca sama ke depan dan ke belakang | 11, 101, 131, 151, 181 |
| Prima aman | Prima p di mana (p−1)/2 juga prima | 5, 7, 11, 23, 47, 59 |
Prima Mersenne (2ⁿ − 1) sangat penting karena dapat diuji untuk prima menggunakan tes Lucas-Lehmer yang efisien. Proyek GIMPS (Great Internet Mersenne Prime Search) menggabungkan komputasi terdistribusi di seluruh dunia untuk menemukan prima Mersenne baru. Pada tahun 2024, prima Mersenne terbesar yang diketahui adalah 2^136,279,841 − 1, dengan lebih dari 41 juta digit desimal.
Prima kembar (pasang yang berbeda oleh 2) dikonjekturkan untuk tak terhingga (Konjektur Prima Kembar), tetapi ini masih belum terbukti — salah satu masalah terbuka yang paling terkenal dalam matematika. Pada tahun 2013, Yitang Zhang membuktikan hasil yang lebih lemah bahwa ada pasang prima tak terhingga yang berbeda oleh paling banyak 70 juta, yang kemudian diperbaiki menjadi 246.
Distribusi Bilangan Prima
Bilangan prima menjadi kurang sering muncul ketika bilangan semakin besar, tetapi distribusinya mengikuti pola statistik yang dijelaskan oleh Teorema Bilangan Prima:
Teorema Bilangan Prima (dibuktikan secara mandiri oleh Hadamard dan de la Vallée-Poussin pada tahun 1896) menyatakan bahwa jumlah bilangan prima hingga N, yang ditulis π(N), adalah sekitar N / ln(N) untuk N besar:
| N | π(N yang sebenarnya | Approximate N/ln(N) | Density |
|---|---|---|---|
| 100 | 25 | 21,7 | 1 dalam 4 |
| 1.000 | 168 | 144,8 | 1 dalam 6 |
| 10.000 | 1.229 | 1.085,7 | 1 dalam 8 |
| 100.000 | 9.592 | 8.685,9 | 1 dalam 10 |
| 1.000.000 | 78.498 | 72.382,4 | 1 dalam 13 |
| 1.000.000.000 | 50.847.534 | 48.254.942 | 1 dalam 20 |
Hipotesis Riemann — salah satu Masalah Hadiah Milenium dengan hadiah $1 juta — mengenai distribusi bilangan prima yang tepat. Ia mengandaikan bahwa semua nol non-trivial fungsi zeta Riemann memiliki bagian riil 1/2. Ini terkait dengan bagaimana "acak" distribusi bilangan prima muncul — hipotesis memprediksi keoptimalan dalam kesenjangan prima.
Frequently Asked Questions
Apakah 1 adalah bilangan prima?
Tidak. Menurut konvensi matematika modern, 1 bukanlah bilangan prima atau komposit. Menghilangkan 1 dari bilangan prima menjaga keunikan faktorisasi prima (Teorema Dasar Arithmetika) — jika 1 adalah prima, maka setiap bilangan memiliki faktorisasi yang tak terhingga (misalnya, 6 = 2×3 = 1×2×3 = 1×1×2×3 = ...). Sejarahnya, beberapa matematikawan mempertimbangkan 1 sebagai prima, tetapi definisi modernnya menghilangkannya.
Bilangan prima terbesar yang diketahui?
Sebagai tahun 2024, bilangan prima terbesar yang diketahui adalah 2^136,279,841 − 1 (bilangan Mersenne prima), ditemukan pada Oktober 2024. Bilangan ini memiliki lebih dari 41 juta digit. Proyek Great Internet Mersenne Prime Search (GIMPS) menemukan sebagian besar rekaman prima menggunakan komputasi terdistribusi dari sukarelawan di seluruh dunia. Bilangan-bilangan prima yang sangat besar ini tidak memiliki aplikasi praktis — pencarian mereka hanya merupakan eksplorasi matematika.
Apakah ada pola dalam bilangan prima?
Bilangan prima tampak tidak teratur, tetapi pola ada. Semua bilangan prima > 5 berakhiran 1, 3, 7, atau 9 (tidak pernah 0, 2, 4, 5, 6, 8). Semua bilangan prima > 3 dapat ditulis dalam bentuk 6k±1. Bilangan prima kembar (berbeda 2, seperti 11 dan 13) tampak terus-menerus (konjektur Bilangan Prima Kembar yang tidak terbukti). Teorema Bilangan Prima menjelaskan kepadatan statistik bilangan prima di sekitar N sekitar 1/ln(N).
Apakah 2 adalah bilangan prima?
Ya, 2 adalah prima — dan itu adalah satu-satunya bilangan prima genap. 2 memiliki dua faktor (1 dan 2), memenuhi definisi. Setiap bilangan genap lainnya dapat dibagi oleh 2, membuatnya komposit. Kepriamana 2 adalah kasus khusus yang sering perlu ditangani terpisah dalam algoritma dan bukti.
Cara apa yang paling cepat untuk memeriksa apakah sebuah bilangan adalah prima?
Untuk bilangan kecil (hingga ~10^12): pembagian coba yang diperbaiki hanya sampai √n menggunakan pola 6k±1. Untuk bilangan sedang: tes prima Miller-Rabin dengan beberapa saksi adalah probabilistik tetapi sangat cepat. Untuk bilangan sangat besar (ukuran kriptografi, 1000+ digit): tes probabilistik seperti Miller-Rabin dengan banyak saksi acak, atau tes AKS untuk bukti deterministik.
Apakah itu celah prima?
Celah prima adalah perbedaan antara dua bilangan prima berurutan. Celah prima terkecil adalah 1 (antara 2 dan 3), dan semua bilangan prima lainnya memiliki celah minimal 2 (karena salah satu harus ganjil). Celah-celah prima tumbuh perlahan-lahan secara rata: di sekitar N, rata-rata celah antara prima adalah ln(N). Celah prima yang sangat besar ada — ada urutan panjang bilangan komposit (n!+2, n!+3, ..., n!+n adalah semua komposit untuk setiap n).
Faktor prima dari 100?
100 = 2 × 50 = 2 × 2 × 25 = 2 × 2 × 5 × 5 = 2² × 5². Faktor prima dari 100 adalah 2 dan 5. Faktorisasi ini menjelaskan mengapa 100 dapat dibagi dengan 1, 2, 4, 5, 10, 20, 25, 50, dan 100 — setiap pembagi mewakili kombinasi 2⁰˒¹˒² dan 5⁰˒¹˒².
Apakah konjektur Goldbach?
Konjektur Goldbach (1742) menyatakan bahwa setiap bilangan genap yang lebih besar dari 2 dapat ditulis sebagai jumlah dua bilangan prima. Misalnya: 4=2+2, 6=3+3, 8=3+5, 10=3+7, 100=3+97=11+89=17+83. Ini telah diverifikasi secara komputasional hingga 4×10^18 tetapi masih belum terbukti. Ini adalah salah satu masalah yang paling tua dan paling terkenal yang belum terpecahkan dalam teori bilangan.
Berapa banyak bilangan prima?
Ada bilangan prima yang tak terhingga — Euclid membuktikan ini sekitar 300 SM. Bukti oleh kontradiksi: jika bilangan prima adalah terbatas, maka produknya plus 1 adalah bilangan prima atau memiliki faktor prima yang tidak ada dalam daftar yang dianggap lengkap, sebuah kontradiksi. Meskipun bilangan prima menjadi kurang padat pada bilangan yang lebih besar, mereka tidak pernah berhenti. Ada tepatnya 78,498 bilangan prima di bawah 1,000,000 dan 5,761,455 bilangan prima di bawah 100,000,000.
Primes dalam Teori Bilangan dan Masalah yang Belum Terpecahkan
Angka prima berada di pusat beberapa masalah matematika yang paling indah dan paling menantang untuk diselesaikan. Pemahaman tentang pertanyaan terbuka ini memberikan cahaya tentang seberapa banyak yang kita ketahui tentang prima — dan seberapa banyak yang masih misterius meskipun telah berusaha selama abad-abad.
Hipotesis Riemann (1859): Fungsi zeta Riemann ζ(s) = Σ(1/nˢ) terkait dengan distribusi prima melalui nolnya. Hipotesis menyatakan bahwa semua nol yang tidak trivial berada di garis kritis Re(s) = 1/2. Jika benar, itu akan memberikan deskripsi yang paling akurat mungkin tentang bagaimana prima didistribusikan. Lebih dari 10 triliun nol telah dihitung dan semua berada di garis kritis — tetapi tidak ada bukti yang ada. Ini adalah Masalah Hadiah Milenium dari Institut Matematika Clay.
Twin Prime Conjecture: Apakah ada banyak pasang prima (p, p+2) — seperti (11,13), (17,19), (41,43), (101,103)? Konjektur mengatakan ya, tetapi masih belum terbukti. Pada 2013, Yitang Zhang's breakthrough membuktikan bahwa ada banyak pasang prima dengan selisih maksimum 70 juta — sebuah batas yang pertama kali terukur. Proyek Polymath kemudian mengurangi batas ini menjadi 246, sehingga kita tahu ada banyak pasang prima dengan selisih ≤ 246. Selisih 2 masih belum terbukti.
Konjektur Goldbach (1742): Setiap bilangan genap yang lebih besar dari 2 adalah hasil dari dua prima. Diperiksa secara komputasional hingga 4 × 10^18. Setiap bilangan genap yang dicoba hingga saat ini memenuhi — sering kali dalam banyak cara (100 = 3+97 = 11+89 = 17+83 = 29+71 = 41+59 = 47+53). Namun, tidak ada bukti yang mencakup semua bilangan genap. Konjektur "lemah Goldbach" (setiap bilangan ganjil ≥ 7 adalah hasil dari tiga prima) dibuktikan pada 2013 oleh Harald Helfgott.
Prima Mersenne dan bilangan sempurna: Sebuah prima Mersenne adalah salah satu bentuk 2ⁿ − 1 (di mana n sendiri harus prima). Beberapa yang pertama adalah: 3, 7, 31, 127, 8191. Hanya 52 yang diketahui pada 2024. Prima Mersenne terkait dengan bilangan sempurna: setiap prima Mersenne menghasilkan bilangan sempurna genap melalui rumus 2^(p−1) × (2^p − 1). Bilangan 28 = 4 × 7 (menggunakan prima Mersenne 7) dan 496 = 16 × 31 (menggunakan prima Mersenne 31) adalah bilangan sempurna. Apakah ada banyak prima Mersenne? Tidak diketahui.
Konjektur ABC dan implikasinya: Konjektur ABC (ditetapkan pada 1985) adalah hubungan yang dalam tentang faktorisasi prima dari tiga bilangan a + b = c. Jika dibuktikan, itu akan mengimplikasikan Teorema Fermat terakhir dan banyak hasil lainnya sebagai korollar yang mudah. Pada 2012, Shinichi Mochizuki menerbitkan bukti yang diklaim menggunakan teori Teichmüller inter-universal — tetapi bukti itu begitu unik dan kompleks sehingga komunitas matematika telah berdebat tentang kevaliditasnya selama lebih dari satu dekade, dengan beberapa matematikawan menerima dan lainnya menemukan celah.
Angka prima tetap menjadi misteri matematika yang paling akhir: sederhana untuk didefinisikan (sebuah bilangan dengan faktor yang tepat dua), namun distribusinya kompleks cukup untuk melandasi masalah yang belum terpecahkan yang telah menantang pikiran matematikawan terbesar selama abad-abad. Setiap rekor baru prima yang ditemukan, setiap verifikasi komputasional dari konjektur hingga batas baru, dan setiap bukti parsial meningkatkan pemahaman kita — sementara mengingatkan kita betapa banyak yang masih perlu ditemukan.