Penyemak Nombor Perdana

Nombor perdana mempunyai tepat dua pembahagi: 1 dan dirinya sendiri.\n\nNombor perdana yang pertama ialah 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...\n\nNombor perdana merupakan asas binaan bagi semua integer.

Setiap integer > 1 boleh dinyatakan secara unik sebagai hasil darab nombor perdana.\n\nSebagai contoh, 60 = 2² × 3 × 5.\n\nIni adalah asas penting dalam matematik dan kriptografi.

Untuk menyemak sama ada sesuatu nombor n adalah nombor perdana, uji sama ada sebarang integer antara 2 dan punca kuasa dua bagi n boleh membahagikannya dengan tepat; jika tiada, n ialah nombor perdana.

Mula-mula selesaikan kes-kes kecil:

• nombor di bawah 2 bukan nombor perdana
• 2 dan 3 adalah nombor perdana
• sebarang nombor genap melebihi 2 ialah nombor gubahan

Kemudian uji pembahagi ganjil sehingga √n, kerana pembahagi sentiasa datang berpasangan di mana ahli yang lebih kecil tidak boleh melebihi punca kuasa dua.

Sebagai contoh, menyemak 97 hanya memerlukan ujian ke atas 3, 5, dan 7 (memandangkan √97 ≈ 9.85), dan tiada satu pun yang membahagikannya dengan tepat, maka 97 ialah nombor perdana. Wolfram MathWorld menerangkan kaedah ini sebagai pembahagian cubaan (trial division), iaitu ujian keperdanan yang paling langsung.

Kaedah punca kuasa dua bermaksud anda hanya perlu menguji pembahagi berpotensi sehingga √n dan bukannya sehingga ke n.

Sebabnya adalah jika n = a × b, maka sekurang-kurangnya satu daripada faktor a atau b mestilah kurang daripada atau sama dengan √n; jika tidak, hasil darab mereka akan melebihi n. Oleh itu, jika tiada faktor ditemui di bawah √n, tiada faktor yang lebih besar akan wujud.

Ini mengurangkan beban kerja secara drastik: menyemak sama ada 9,973 adalah nombor perdana hanya memerlukan ujian pembahagi sehingga sekitar 99, bukannya hampir 10,000.

Khan Academy menggunakan hujah berpasangan ini untuk menerangkan sebab pembahagian cubaan berhenti pada punca kuasa dua, sekali gus menjadikan semakan keperdanan secara manual lebih praktikal.

Saringan Eratosthenes mencari semua nombor perdana sehingga had N dengan menandakan gandaan bagi setiap nombor perdana sebagai nombor gubahan secara berulang.

Mula dengan senarai integer dari 2 hingga N. Ambil 2, tandakan 4, 6, 8, ... sebagai gubahan; beralih ke nombor seterusnya yang tidak ditanda, iaitu 3, dan tandakan 6, 9, 12, ...; teruskan dengan 5, 7, dan seterusnya. Nombor yang kekal tidak ditanda ialah nombor perdana.

Apabila digunakan sehingga 30, saringan ini meninggalkan 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Dinamakan sempena ahli matematik Yunani Eratosthenes dari Cyrene, algoritma ini (yang didokumentasikan oleh Encyclopaedia Britannica) merupakan salah satu cara tertua dan paling cekap untuk menyenaraikan nombor perdana dalam sesuatu julat.

Teorem Asas Aritmetik menyatakan bahawa setiap integer yang lebih besar daripada 1 sama ada merupakan nombor perdana atau boleh ditulis sebagai hasil darab nombor perdana dalam satu cara sahaja, tanpa mengira tertib faktor-faktor tersebut.

Sebagai contoh, 360 = 2³ × 3² × 5, dan tiada gabungan nombor perdana lain yang menghasilkan 360 apabila didarabkan. Keunikan inilah sebabnya nombor perdana dipanggil sebagai blok binaan bagi integer.

Menurut Wolfram MathWorld, teorem ini menjadi asas kepada pemfaktoran perdana, pengiraan pembahagi sepunya terbesar, dan aritmetik modular.

Kalkulator kami menggunakannya apabila ia memfaktorkan sesuatu nombor, sekali gus menjamin bahawa penghuraian perdana yang dikembalikan adalah satu-satunya yang mungkin.

Nombor perdana kembar ialah pasangan nombor perdana yang mempunyai perbezaan tepat sebanyak 2, seperti (3, 5), (5, 7), (11, 13), (17, 19), dan (29, 31).

Jurang antara nombor perdana yang berturutan secara amnya meningkat apabila nombor menjadi lebih besar, walaupun nombor perdana kembar terus muncul. Sama ada wujudnya nombor perdana kembar yang tidak terhingga adalah Konjektur Perdana Kembar yang terkenal dan masih belum terbukti.

On-Line Encyclopedia of Integer Sequences (OEIS) mengkatalogkan ahli yang lebih kecil bagi pasangan nombor perdana kembar dalam jujukan A001359.

Memahami jurang perdana membantu menjelaskan mengapa nombor perdana menjadi lebih jarang: menghampiri satu juta, nombor perdana secara puratanya berjarak kira-kira 14 antara satu sama lain, satu trend yang diterangkan oleh Teorem Nombor Perdana dalam NIST Digital Library of Mathematical Functions.

Nombor perdana memacu kriptografi moden, terutamanya penyulitan RSA, yang melindungi perbankan dalam talian, laman web HTTPS, dan tandatangan digital. RSA bergantung pada hakikat bahawa mendarab dua nombor perdana yang besar adalah mudah, tetapi memfaktorkan semula hasil darab tersebut kepada nombor perdana asal adalah sangat sukar dari segi pengiraan.

Selain keselamatan, nombor perdana muncul dalam:

• saiz jadual cincangan (jadual dengan panjang perdana mengurangkan perlanggaran data)
• penjanaan nombor rawak semu (pseudo-random)
• kod pembetulan ralat
• kitaran hayat keriang (cicada) yang berkembang mengikut tahun nombor perdana untuk mengelakkan pemangsa

Britannica menyatakan bahawa pemfaktoran perdana juga memudahkan fungsi kalkulator pecahan dan mengira gandaan sepunya terkecil. Kalkulator ini menyokong tugas-tugas tersebut dengan memfaktorkan nombor dan menjana nombor perdana untuk reka bentuk algoritma serta kerja rumah matematik.

Sesuatu nombor perdana mempunyai tepat dua pembahagi positif yang berbeza, iaitu 1 dan dirinya sendiri, manakala nombor gubahan mempunyai lebih daripada dua pembahagi.

Sebagai contoh, 13 ialah nombor perdana (pembahagi 1 dan 13), dan 12 ialah nombor gubahan (pembahagi 1, 2, 3, 4, 6, 12). Nombor 1 bukanlah nombor perdana mahupun nombor gubahan, kerana ia hanya mempunyai satu pembahagi.

Ketetapan ini memastikan Teorem Asas Aritmetik kekal kemas: jika 1 dikira sebagai nombor perdana, pemfaktoran tidak lagi unik kerana anda boleh memasukkan seberapa banyak nombor 1 yang anda mahu.

Encyclopaedia Britannica dan Khan Academy kedua-duanya menekankan perbezaan ini, itulah sebabnya alat kami melabelkan 1 secara berasingan daripada nombor perdana dan nombor gubahan.

Nombor perdana Mersenne ialah nombor perdana dalam bentuk 2^p − 1, di mana eksponen p itu sendiri merupakan nombor perdana; contohnya termasuk 3 (2² − 1), 7 (2³ − 1), 31 (2⁵ − 1), dan 127 (2⁷ − 1).

Bagaimanapun, tidak semua eksponen perdana menghasilkan nombor perdana: 2¹¹ − 1 = 2047 = 23 × 89 ialah nombor gubahan.

Nombor perdana Mersenne adalah penting kerana ujian pantas yang dipanggil ujian Lucas-Lehmer menjadikannya lebih mudah untuk disahkan berbanding nombor biasa, jadi nombor perdana terbesar yang diketahui hampir sentiasa merupakan nombor perdana Mersenne dengan berpuluh-puluh juta digit.

Great Internet Mersenne Prime Search (GIMPS) menyelaraskan sukarelawan untuk menemuinya. Jujukan OEIS A000668 menyenaraikan nombor perdana Mersenne yang diketahui.

• Kesilapan paling biasa adalah menganggap 1 sebagai nombor perdana; ia bukan, kerana nombor perdana mesti mempunyai tepat dua pembahagi.
• Satu lagi kesilapan adalah terlupa bahawa 2 ialah satu-satunya nombor perdana genap, jadi orang ramai tersilap melangkaunya atau tersilap menganggap nombor genap lain mungkin nombor perdana.
• Kesilapan ketiga adalah menghentikan pembahagian cubaan terlalu awal atau terlalu lewat: anda mesti menguji semua pembahagi sehingga √n, bukan sekadar beberapa nombor kecil.
• Orang ramai juga keliru antara pemfaktoran perdana dengan menyenaraikan semua faktor; 12 mempunyai faktor 1, 2, 3, 4, 6, 12 tetapi pemfaktoran perdananya hanyalah 2² × 3.
• Akhir sekali, menganggap setiap nombor dalam bentuk 6k ± 1 sebagai nombor perdana adalah salah; 25 = 6(4) + 1 ialah nombor gubahan.