Pemeriksa Bilangan Perdana
Periksa jika nombor adalah nombor perdana dan cari faktornya. Gunakan pemeriksa nombor perdana percuma ini untuk segera menguji mana-mana nombor dan mencari semua faktor perdana. Tiada pendaftaran yang diperlukan.
Apakah nombor perdana?
Bilangan prima adalah nombor asli yang lebih besar daripada 1 yang mempunyai dua faktor yang berbeza: 1 dan dirinya sendiri. Bilangan 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 utama mengenai nombor perdana:
- 2 adalah satu-satunya nombor perdana genap.Setiap nombor genap yang lain boleh dibahagikan dengan 2, jadi ia mempunyai lebih daripada dua faktor.
- 1 bukan nombor perdanadengan konvensi moden. Mengeksklusi 1 mengekalkan keunikan pemfaktoran utama (Teorema Dasar Aritmetik).
- Nombor prima tidak terhingga.Euclid membuktikan ini sekitar 300 SM: menganggap senarai yang terhingga semua nombor perdana p1, p2, ..., pn. Kemudian nombor (p1 x p2 x ... x pn) + 1 sama ada perdana sendiri atau mempunyai faktor perdana yang tidak dalam senarai - kontradiksi. Oleh itu senarai itu tidak terhingga.
- Apabila bilangan menjadi lebih besar, bilangan prima menjadi kurang kerap -- tetapi merekaJangan berhentiTerdapat 25 bilangan prima di bawah 100, 168 di bawah 1,000, dan 78,498 di bawah 1,000,000.
A nombor kompositadalah mana-mana bilangan bulat positif yang lebih besar daripada 1 yang bukan nombor perdana - ia mempunyai sekurang-kurangnya satu faktor selain 1 dan dirinya sendiri. Nombor 12 adalah komposit kerana 12 = 2 x 6 = 3 x 4 = 2 x 2 x 3. Setiap nombor komposit mempunyai faktorisasi perdana yang unik (Teorema Dasar Aritmetik).
Cara Memeriksa Jika Nombor adalah Perdana
Terdapat beberapa kaedah untuk ujian primaliti, mulai dari pembahagian percubaan sederhana hingga algoritma kebarangkalian lanjutan:
Bahagian Percubaan (kaedah asas):Uji sama ada mana-mana bilangan bulat dari 2 hingga √n membahagikan n secara merata. Jika tidak ada, n adalah nombor perdana. Anda hanya perlu memeriksa hingga √n kerana jika n = a x b dengan a <= b, maka a <= √n. Jika tiada pembahagi ditemui hingga √n, tidak ada di atas √n juga.
Bahagian percubaan yang dioptimumkan:Selepas memeriksa pembahagian dengan 2, hanya menguji nombor ganjil. Selanjutnya: periksa 2, 3, kemudian hanya nombor bentuk 6k + / -1 (kerana semua nombor prima > 3 adalah bentuk ini). Ini mengurangkan bilangan ujian sebanyak 66% berbanding dengan pembahagian percubaan naif.
| Bilangan | √n (kira-kira) | Pembahagian ujian sehingga | Perdana? |
|---|---|---|---|
| 97 | 9.85 | 2, 3, 5, 7 | Ya (tidak dibahagikan secara merata) |
| 91 | 9.54 | 2, 3, 5, 7 | No (7 x 13 = 91) |
| 1,009 | 31.76 | Sehingga 31 | Ya (utama) |
| 1,001 | 31.64 | Sehingga 31 | No (7 x 11 x 13 = 1,001) |
| 7,919 | 88.99 | Sehingga 89 | Ya (prima ke-1,000) |
Untuk bilangan besar (ratusan digit), pembahagian percubaan tidak dapat dilakukan secara komputasi.Ujian primaliti Miller-Rabin(probabilistik, digunakan dalam kriptografi) danUjian primaliti AKS(deterministic polynomial-time, 2002) digunakan sebagai gantinya.
Pemfaktoran Perdana
Setiap nombor komposit boleh ditulis sebagai satu produk nombor perdana yang unik - pemfaktoran perdana. Ini dijamin oleh Teorema Fundamental Aritmetik. Untuk mencari pemfaktoran perdana, bahagi berulang kali dengan faktor perdana terkecil:
| Bilangan | Pemfaktoran utama | Pembahagian pokok faktor |
|---|---|---|
| 12 | 22 x 3 | 12 -> 4x3 -> 2x2x3 |
| 60 | 22 x 3 x 5 | 60 -> 4x15 -> 22x3x5 |
| 100 daripada 100 | 22 x 52 | 100 -> 4x25 -> 22x52 |
| 360 | 23 x 32 x 5 | 360 -> 8x45 -> 23x32x5 |
| 1,024 | 210 | Semua faktor utama adalah 2 |
| 2,310 | 2 x 3 x 5 x 7 x 11 | Perkalian 5 nombor perdana pertama |
Faktorisasi prima digunakan untuk mencari pembaha biasa terbesar (GCD) dan kelipatan biasa terkecil (LCM) nombor. GCD ((12, 18) = 22 x 3? Tidak -- mengambil kuasa minimum bilangan prima yang dikongsi: GCD = 21 x 31 = 6. LCM mengambil kuasa maksimum: LCM ((12, 18) = 22 x 32 = 36.
Mengapa nombor perdana penting: Aplikasi dalam Matematik dan Teknologi
Bilangan prima adalah "atom" aritmetik - Teorema Dasar Aritmetik menyatakan bahawa setiap bilangan bulat positif yang lebih besar daripada 1 sama ada merupakan bilangan prima atau boleh dinyatakan sebagai hasil tunggal bilangan prima. Keunikan ini menjadikan bilangan prima sebagai blok bangunan yang tidak dapat direduksi dari semua nombor.
Keselamatan internet modenPenyulitan RSA (digunakan untuk HTTPS, penyulitan e-mel, dan tandatangan digital) menghasilkan kunci awam dengan mengalikan dua bilangan prima besar p dan q untuk membentuk n = p x q. Kunci penyulitan dan penyahsulitan dikira menggunakan aritmetik modular dengan n. Keselamatan bergantung padamasalah pemfaktoran bilangan bulat: diberikan n (nombor 2048-bit dengan ~ 617 digit perpuluhan), mencari p dan q tidak dapat dihitung dengan teknologi semasa.
Pertukaran kunci Diffie-Hellmanmenggunakan modul utama yang besar untuk perjanjian kunci yang selamat. Apabila anda menyambung ke laman web melalui HTTPS, nombor utama secara senyap melindungi data anda dalam masa nyata.
Jadual hashmenggunakan array bersaiz prima untuk meminimumkan perlanggaran. Apabila fungsi hash memetakan kekunci ke indeks baldi, menggunakan bilangan baldi utama memastikan pengedaran yang lebih baik kerana bilangan prima tidak mempunyai faktor yang dapat mewujudkan corak perlanggaran sistematik.
Penjana nombor rawak palsu(PRNGs) menggunakan modul prima dalam penjana kongruen linear dan algoritma lain.
Jenis-jenis khas premium
Dalam set bilangan prima yang tak terhingga, subset tertentu mempunyai sifat atau kepentingan khas:
| Jenis | Definisi | Contoh |
|---|---|---|
| Bilangan prima kembar | Premis berbeza dengan 2 | (3,5), (11,13), (17,19), (41,43) |
| Bilangan prima Mersenne | Premium dalam bentuk 2n - 1 | 3, 7, 31, 127, 8,191 |
| Bilangan prima Fermat | Prima dalam bentuk 2^(2n) + 1 | 3, 5, 17, 257, 65,537 |
| Bilangan prima Sophie Germain | p dan 2p+1 adalah kedua-dua nombor perdana | 2, 3, 5, 11, 23, 29 |
| Bilangan prima palindromik | Premis yang membaca sama ke hadapan / ke belakang | 11, 101, 131, 151, 181 |
| Bilangan prima yang selamat | Nombor prima p di mana (p-1) / 2 juga nombor perdana | 5, 7, 11, 23, 47, 59 |
Bilangan prima MersenneProjek GIMPS (Great Internet Mersenne Prime Search) memanfaatkan pengkomputeran diedarkan di seluruh dunia untuk mencari bilangan prima Mersenne baru. Pada tahun 2024, bilangan prima Mersenne terbesar yang diketahui adalah 2 ^ 136,279,841 - 1, dengan lebih dari 41 juta digit perpuluhan.
Bilangan prima kembarPada tahun 2013, Yitang Zhang membuktikan hasil yang lebih lemah bahawa terdapat banyak pasangan perdana yang berbeza dengan 70 juta, yang kemudiannya diperbaiki menjadi 246.
Pengedaran Bilangan Prima
Bilangan prima menjadi kurang kerap apabila bilangan menjadi lebih besar, tetapi pengedaran mereka mengikuti corak statistik yang diterangkan oleh Teorema Bilangan Prima:
PerkhidmatanTeorema Bilangan Perdana(dibuktikan secara bebas oleh Hadamard dan de la Vallée-Poussin pada tahun 1896) menyatakan bahawa bilangan prima sehingga N, yang dilambangkan π ((N), adalah kira-kira N / ln ((N) untuk N besar:
| N | Sebenarnya π ((N) | Kira-kira N/ln (N) | Ketumpatan |
|---|---|---|---|
| 100 daripada 100 | 25 | 21.7 | 1 daripada 4 |
| 1,000 ringgit | 168 | 144.8 | 1 daripada 6 |
| 10,000 orang | 1,229 | 1,085.7 | 1 daripada 8 |
| Seratus ribu | 9,592 | 8,685.9 | 1 daripada 10 |
| 1 juta | 78,498 | 72,382.4 | 1 daripada 13 |
| 1,000,000,000 | 50,847,534 | 48,254,942 | 1 daripada 20 |
PerkhidmatanHipotesis Riemann-- salah satu masalah Hadiah Milenium dengan hadiah $1 juta -- berkaitan dengan pengedaran nombor perdana yang tepat. Ia menjangkakan bahawa semua sifar yang tidak penting dari fungsi zeta Riemann mempunyai bahagian nyata 1/2. Ini berkaitan dengan bagaimana "random" pengedaran nombor perdana muncul -- hipotesis meramalkan keteraturan optimum dalam jurang perdana.
Soalan yang Sering Diajukan
Adakah 1 nombor perdana?
Tidak. Menurut konvensyen matematik moden, 1 bukanlah nombor perdana atau komposit. Menyingkirkan 1 dari nombor perdana mengekalkan keunikan pemfaktoran perdana (Teorema Dasar Aritmetik) - jika 1 adalah nombor perdana, setiap nombor akan mempunyai banyak pemfaktoran yang tidak terhingga (contohnya, 6 = 2x3 = 1x2x3 = 1x1x2x3 = ...).
Apakah bilangan prima terbesar yang diketahui?
Pada tahun 2024, nombor perdana terbesar yang diketahui ialah 2 ^ 136,279,841 - 1 (nombor perdana Mersenne), yang ditemui pada bulan Oktober 2024. Ia mempunyai lebih daripada 41 juta digit. Projek Great Internet Mersenne Prime Search (GIMPS) mendapati kebanyakan nombor perdana menggunakan pengkomputeran diedarkan dari sukarelawan di seluruh dunia. Nombor perdana yang sangat besar ini tidak mempunyai aplikasi praktikal - carian mereka adalah penerokaan matematik semata-mata.
Adakah terdapat corak dalam nombor perdana?
Semua nombor perdana > 5 berakhir dengan 1, 3, 7, atau 9 (tidak pernah 0, 2, 4, 5, 6, 8). Semua nombor perdana > 3 adalah bentuk 6k + / 1. nombor perdana kembar (berbeza dengan 2, seperti 11 dan 13) nampaknya berterusan selama-lamanya (konjeksi nombor perdana kembar yang tidak terbukti). Teorema nombor perdana menggambarkan kepadatan statistik nombor perdana berhampiran N sebagai kira-kira 1/lnN.
Adakah 2 nombor perdana?
Ya, 2 adalah nombor perdana -- dan ia adalah satu-satunya nombor perdana genap. 2 mempunyai dua faktor (1 dan 2), memenuhi definisi. Setiap nombor genap yang lain boleh dibahagikan dengan 2, menjadikannya komposit. Keaslian 2 adalah kes khas yang sering perlu ditangani secara berasingan dalam algoritma dan bukti.
Bagaimana primality digunakan dalam penyulitan?
Penyulitan RSA menghasilkan pasangan kunci dengan: (1) memilih dua bilangan prima besar p dan q (masing-masing 1024+ bit), (2) mengira n = pxq, (3) memperoleh kunci penyulitan e dan kunci penyahsulitan d menggunakan aritmetik modular. Sesiapa sahaja boleh menyulitkan dengan n dan e (kunci awam), tetapi hanya pemegang p dan q (atau d) yang dapat menyahsulitkan. Keselamatan bergantung pada kesukaran pengiraan faktor n kembali ke pxq.
Apakah cara terpantas untuk memeriksa jika nombor adalah nombor perdana?
Untuk nombor kecil (sehingga ~ 10 ^ 12): pembahagian percubaan yang dioptimumkan hanya memeriksa hingga √n menggunakan corak 6k + / -1. Untuk nombor sederhana: Ujian primaliti Miller-Rabin dengan beberapa saksi adalah probabilistik tetapi sangat cepat. Untuk nombor yang sangat besar (ukuran kriptografi, 1000+ digit): ujian probabilistik seperti Miller-Rabin dengan banyak saksi rawak, atau ujian AKS untuk bukti deterministik.
Apakah jurang perdana?
Jurang prima adalah perbezaan antara dua nombor perdana berturut-turut. Jurang perdana terkecil adalah 1 (antara 2 dan 3), dan semua nombor perdana berturut-turut yang lain mempunyai jurang sekurang-kurangnya 2 (kerana satu mesti ganjil). Jurang tumbuh perlahan-lahan secara purata: berhampiran N, jurang purata antara nombor perdana adalah ln(N). Jurang perdana yang luar biasa besar wujud - terdapat urutan nombor komposit berturut-turut yang panjang (n! + 2, n! + 3, ..., n! + n semuanya komposit untuk mana-mana n).
Apakah faktor utama 100?
100 = 2 x 50 = 2 x 2 x 25 = 2 x 2 x 5 x 5 = 22 x 52. Faktor utama 100 adalah 2 dan 5. Faktorisasi ini menjelaskan mengapa 100 dibahagikan secara merata dengan 1, 2, 4, 5, 10, 20, 25, 50, dan 100 - setiap pembahagi sepadan dengan kombinasi 20 1 2 dan 50 1 2.
Apakah dugaan Goldbach?
Konjektur Goldbach (1742) menyatakan bahawa setiap bilangan bulat genap yang lebih besar daripada 2 boleh dinyatakan sebagai jumlah dua bilangan prima. Contohnya: 4=2+2, 6=3+3, 8=3+5, 10=3+7, 100=3+97=11+89=17+83. Ia telah disahkan secara pengiraan sehingga 4x10^18 tetapi masih belum dibuktikan. Ia adalah salah satu masalah tertua dan paling terkenal yang belum diselesaikan dalam teori bilangan.
Berapa banyak nombor perdana yang ada?
Terdapat bilangan prima yang tak terhingga -- Euclid membuktikan ini sekitar 300 SM. Bukti dengan kontradiksi: jika bilangan prima adalah terhingga, produk mereka ditambah 1 akan sama dengan bilangan prima atau mempunyai faktor utama yang tidak dalam senarai lengkap, kontradiksi. Walaupun bilangan prima menjadi kurang padat pada bilangan yang lebih besar, mereka tidak pernah berhenti. Terdapat tepat 78,498 bilangan prima di bawah 1,000,000 dan 5,761,455 bilangan prima di bawah 100,000,000.
Prima dalam Teori Bilangan dan Masalah yang Tidak Terpecahkan
Bilangan prima terletak di tengah-tengah beberapa masalah matematik yang paling indah dan paling keras kepala yang belum diselesaikan. Memahami soalan-soalan terbuka ini menerangi berapa banyak yang kita tahu tentang bilangan prima -- dan berapa banyak yang masih misteri walaupun beratus-ratus tahun usaha.
Hipotesis Riemann (1859):Fungsi zeta Riemann ζ(s) = Σ(1/ns) menyambung kepada pengedaran bilangan prima melalui sifarnya. Hipotesis menyatakan bahawa semua sifar yang tidak sepele terletak di garisan kritikal Re(s) = 1/2. Jika benar, ia akan memberikan keterangan yang paling tepat tentang bagaimana bilangan prima diedarkan. Lebih daripada 10 trilion sifar telah dikira dan semuanya terletak di garisan kritikal - tetapi tidak ada bukti. Ia adalah Masalah Hadiah Milenium dengan anugerah $ 1 juta dari Institut Matematik Clay.
Dugaan Twin Prime:Adakah terdapat banyak pasangan nombor perdana (p, p + 2) - seperti (11,13), (17,19), (41,43), (101,103)? Dugaan mengatakan ya, tetapi ia masih belum terbukti. Pada tahun 2013, terobosan Yitang Zhang membuktikan terdapat banyak pasangan nombor perdana dengan jurang maksimum 70 juta - terhad terhad pertama. Projek Polimatik kemudiannya mengurangkan terhad ini kepada 246, yang bermaksud kita tahu terdapat banyak pasangan nombor perdana dengan jurang <= 246. jurang 2 masih belum terbukti.
Dugaan Goldbach (1742):Setiap bilangan bulat genap yang lebih besar daripada 2 adalah jumlah dua bilangan prima. Diuji secara pengiraan sehingga 4 x 10 ^ 18. Setiap nombor genap yang dicuba setakat ini memuaskannya - selalunya dalam banyak cara (100 = 3 + 97 = 11 + 89 = 17 + 83 = 29 + 71 = 41 + 59 = 47 + 53). Namun tidak ada bukti yang meliputi semua nombor genap. "Rumor Goldbach lemah" (setiap nombor ganjil > = 7 adalah jumlah tiga bilangan prima) telah dibuktikan pada tahun 2013 oleh Harald Helfgott.
Nombor prima Mersenne dan nombor sempurna:Nombor perdana Mersenne adalah salah satu bentuk 2n - 1 (di mana n itu sendiri mestilah nombor perdana). Beberapa yang pertama adalah: 3, 7, 31, 127, 8,191. Hanya 52 yang diketahui pada tahun 2024. Nombor perdana Mersenne disambungkan kepada nombor sempurna: setiap nombor perdana Mersenne menghasilkan nombor sempurna genap melalui formula 2 ^ ((p-1) x (2 ^ p - 1). Nombor 28 = 4 x 7 (menggunakan nombor perdana Mersenne 7) dan 496 = 16 x 31 (menggunakan nombor perdana Mersenne 31) adalah nombor sempurna. Adakah terdapat banyak nombor perdana Mersenne? Tidak diketahui.
Dugaan ABC dan implikasinya:Sangkaan ABC (dinyatakan pada tahun 1985) adalah hubungan yang mendalam mengenai faktorisasi perdana tiga nombor a + b = c. Jika dibuktikan, ia akan menyiratkan Teorema Terakhir Fermat dan banyak hasil lain sebagai koroleri mudah. Pada tahun 2012, Shinichi Mochizuki menerbitkan bukti yang diklaim menggunakan teori Teichmüller Antara-universalnya - tetapi bukti itu begitu baru dan kompleks sehingga komuniti matematik telah memperdebatkan kesahihannya selama lebih dari satu dekad, dengan beberapa ahli matematik menerimanya dan yang lain mencari jurang.
Nombor-nombor perdana tetap menjadi misteri matematik utama: mudah untuk ditakrifkan (nombor dengan dua faktor yang tepat), namun pengedaran mereka cukup kompleks untuk mendasari masalah terbuka yang telah menentang minda matematik terbesar selama berabad-abad. Setiap rekod perdana baru yang ditemui, setiap pengesahan komputasi dugaan kepada had baru, dan setiap bukti separa memajukan pemahaman kita - sambil mengingatkan kita betapa banyak lagi yang perlu ditemui.