Kalkulator Bilangan Prima

n bilangan prima <=> d(n) = 2; previousPrime(97) = 97; nextPrime(97) = 97; nextPrime(1.000.000) = 1.000.003

n

Bilangan bulat yang sedang diuji, dari 2 sampai 1.000.000. Batas bawahnya disengaja dan bukan diwarisi: bilangan prima sebelumnya dari 1 tidak ada, sehingga halaman yang menerima 1 akan punya baris yang tidak bisa diisinya dengan jujur. Apakah 1 bilangan prima adalah pertanyaan definisi, dan jawabannya ada di daftar pertanyaan di bawah dan bukan di kalkulatornya

d(n)

Jumlah pembagi positif, yaitu baris pertama hasilnya dan satu-satunya bukti yang menopang putusannya. d(n) = 2 berarti tepat dua bilangan membaginya, dan itulah definisi bilangan prima. Hitungannya berasal dari rutin teori bilangan bersama, jadi nilainya sama dengan yang dilaporkan halaman faktor dan halaman faktorisasi prima untuk masukan yang sama

d(n) = 2

Ujiannya sendiri, dituliskan sebagai persamaan. Ia kesetaraan dan bukan penghampiran: sebuah bilangan prima jika dan hanya jika ia punya tepat dua pembagi. Untuk 97 pembaginya adalah 1 dan 97, jadi hitungannya 2 dan lencananya berbunyi prima. Untuk 100 pembaginya adalah 1, 2, 4, 5, 10, 20, 25, 50, dan 100, jadi hitungannya 9 dan lencananya berbunyi komposit

previousPrime(n)

Bilangan prima terbesar yang tidak lebih besar daripada n. Batas atasnya inklusif, sehingga ketika n prima jawabannya adalah n itu sendiri. Untuk 100 jawabannya 97; untuk 25 jawabannya 23; untuk 97 jawabannya 97. Selangnya tertutup karena pilihan lainnya menuntut aturan tentang apa yang harus dicetak ketika n sudah prima, dan baris kosong pada panel hasil terbaca sebagai kegagalan dan bukan sebagai fakta

nextPrime(n)

Bilangan prima terkecil yang tidak lebih kecil daripada n, dengan aturan inklusif yang sama di batas bawahnya. Untuk 25 jawabannya 29, untuk 100 jawabannya 101, dan untuk 97 jawabannya 97. Yang ini bisa keluar dari rentang masukannya: nextPrime(1.000.000) adalah 1.000.003, bilangan prima yang lebih besar daripada bilangan mana pun yang diterima halaman ini, dan ia dilaporkan sebagai jawaban dan bukan diperlakukan sebagai di luar batas

1e6 to 1e6 + 100

Daerah di sekitar batas atas masukan, dan alasan ujian tersendiri diperlukan di sana. Bilangan prima di dekat satu juta adalah 999.983 dan 1.000.003, sehingga pencarian dari 1.000.000 harus melihat melewati satu juta ke salah satu arahnya. Rutin yang menghitung pembagi menolak argumen di atas satu juta dan akan melempar kesalahan, jadi pencarian tetangga memakai ujiannya sendiri yang tidak punya batas seperti itu — dan keduanya wajib sepakat di mana pun keduanya bertumpang tindih, dan itulah yang diperiksa oleh baris-baris prima pada contoh-contoh di halaman ini

Memilih modulus adalah alasan paling praktis untuk menginginkan bilangan prima yang dekat dengan bilangan yang sudah Anda pilih. Jumlah slot pada sebuah tabel hash biasanya diambil berupa bilangan prima, karena modulus yang prima menyebarkan kunci-kunci yang punya faktor sama dan tidak membiarkannya bertabrakan; tabel berukuran 1.000 menaruh setiap kelipatan 25 di beberapa slot yang sama, sedangkan tabel berukuran 997 tidak. Naluri yang sama berlaku di kriptografi, ketika kunci dibangun dari bilangan prima yang besar dan berjauhan. Memeriksa apakah sebuah bilangan prima juga memutuskan pertanyaan keterbagian dengan cepat: kalau sebuah bilangan tidak punya pembagi prima sampai akar kuadratnya, ia tidak punya pembagi prima sama sekali, dan lencana di halaman ini menjawabnya dalam satu langkah dan bukan dengan mencoba satu per satu. Sebagian teka-teki memang soal keprimaan semata — bilangan prima kembar, jarak antara bilangan prima yang berurutan, dan apakah sebuah bilangan tertentu merupakan hasil kali dua bilangan prima. Ketika pertanyaannya ternyata menyangkut faktornya sendiri, halaman faktorisasi memecah bilangan itu menjadi bilangan prima dan merupakan persinggahan berikutnya yang wajar; ketika pertanyaannya bilangan mana yang membagi bilangan Anda, halaman faktor mencantumkan semuanya; dan ketika bilangan yang diuji bukan bilangan prima dan Anda ingin tahu dari apa ia tersusun, jumlah pembagi di halaman ini adalah petunjuk pertamanya dan bukan jawaban lengkapnya.

1. Bilangan prima: 97

   1. Uji pembagi 97: 2 tidak membaginya, dan 3, 5, 7, maupun 11 juga tidak
   2. Berhenti di akar kuadratnya: 10 × 10 = 100 sudah melewati 97, jadi tidak ada lagi yang perlu diuji
   3. Satu-satunya pembaginya adalah 1 dan 97, jadi hitungannya 2 dan bilangan itu prima
   4. Bilangan prima sebelumnya adalah 97 itu sendiri, karena 97 sudah prima dan pencariannya inklusif
   5. Bilangan prima berikutnya juga 97, dengan alasan yang sama

   Masukan bawaan, sekaligus gambaran paling bersih dari aturan inklusif itu. Kedua tetangganya kembali sebagai bilangan itu sendiri, yang pada pandangan pertama terlihat seperti kedua baris itu tidak mengerjakan apa pun. Keduanya mengerjakan: bilangan prima terbesar yang tidak lebih besar daripada 97 adalah 97, dan bilangan prima terkecil yang tidak lebih kecil daripada 97 juga 97. Pilihan lainnya — pertidaksamaan yang ketat — akan meninggalkan kedua baris ini tanpa isi tepat pada masukan yang paling diyakini halaman ini, sedangkan baris kosong pada panel hasil terbaca sebagai kesalahan. Kasus ini juga tempat kedua ujian mandiri di halaman ini bertemu: jumlah pembaginya berkata 2, dan pencarian tetangganya menyetujui bahwa 97 prima, dan keduanya memakai kode yang berbeda untuk sampai ke sana.

2. Bilangan komposit: 100

   1. 100 genap, jadi 2 membaginya; ia berakhir dengan 00, jadi 4, 5, 10, 20, 25, dan 50 juga membaginya
   2. Pembaginya adalah 1, 2, 4, 5, 10, 20, 25, 50, dan 100 — ada sembilan
   3. Sembilan lebih besar daripada dua, jadi lencananya berbunyi komposit dan bukan prima
   4. Bilangan prima terbesar yang tidak lebih besar daripada 100 adalah 97; yang terkecil yang tidak lebih kecil daripadanya adalah 101
   5. Kedua tetangganya berada satu langkah di luar bilangan itu, dan itulah penampakan sebuah bilangan komposit yang berada di tengah sebuah jarak

   Kasus yang memperlihatkan kedua tetangganya benar-benar bekerja. Ketika bilangannya komposit, kedua baris itulah keluaran yang berguna, karena keduanya menjawab pertanyaan yang berikutnya ada di kepala pembaca: kalau bukan bilangan ini, lalu bilangan mana? Sembilan puluh tujuh dan seratus satu adalah bilangan prima terdekat, dan 100 berada di antara keduanya. Jumlah pembagi sembilan itu juga layak diperhatikan — ia ganjil, dan itu terjadi tepat ketika bilangannya kuadrat sempurna, dan 100 adalah 10 kuadrat. Jadi sekali melirik hitungannya saja sudah memberi tahu Anda sesuatu tentang bentuk bilangan itu, sebelum ada pemfaktoran yang dikerjakan.

3. Bilangan yang persis melewati bilangan prima: 25

   1. Pembagi 25 adalah 1, 5, dan 25 — ada tiga, karena 5 berpasangan dengan dirinya sendiri
   2. Tiga lebih besar daripada dua, jadi 25 komposit
   3. Telusuri ke bawah dari 25: 24, 23 — 23 prima, jadi itulah bilangan prima sebelumnya
   4. Telusuri ke atas dari 25: 26, 27, 28, 29 — 29 prima, jadi itulah bilangan prima berikutnya
   5. Jaraknya di sini enam seluruhnya: 23 dan 29 mengapit 25

   Kuadrat sempurna, dan itulah sebabnya jumlah pembaginya ganjil, sekaligus kasus ketika kedua tetangganya berada pada jarak yang terlihat berbeda — dua di bawah dan empat di atas. Hitungan tiga itu juga memperlihatkan mengapa dua adalah ambang yang tepat dan bukan hitungan faktor prima: 25 hanya punya satu faktor prima, yaitu 5, tetapi ia bukan bilangan prima, dan jumlah pembagi menangkapnya tanpa perlu melihat faktorisasinya sama sekali.

Masukannya harus bilangan bulat dari 2 sampai 1.000.000. Nol dan satu ditolak, dan satu ditolak dengan alasan yang berbeda daripada nol: ia pertanyaan definisi dan bukan bilangan di luar rentang, dan bilangan prima sebelumnya dari 1 tidak ada. Bilangan negatif ditolak — keprimaan adalah sifat bilangan bulat di atas 1, dan walaupun ada kesepakatan tentang bilangan prima negatif di sebagian cabang matematika, halaman ini tidak mengadopsinya. Bilangan pecahan ditolak dan tidak dibulatkan. Batas satu juta hanya berlaku untuk masukannya; kedua baris tetangganya sah-sah saja melaporkan bilangan prima di luarnya, dan bilangan prima setelah satu juta adalah 1.000.003, yang dilaporkan dan bukan ditolak. Ujian di balik putusannya adalah pembagian percobaan sampai akar kuadrat, yang seketika pada ukuran ini dan tidak ada harapan pada bilangan dua puluh digit, dan batas itu sifat persoalannya dan bukan sifat pelaksanaan halaman ini. Halaman ini melaporkan tiga bilangan dan sebuah lencana: ia tidak mencantumkan pembaginya sendiri, tidak memfaktorkan bilangan komposit, dan menguji satu bilangan pada satu waktu dan bukan satu rentang. Tabel rujukan di bawah berisi baris-baris tetap dan bukan tanggapan atas masukan Anda. Terakhir, sebuah bilangan prima dilaporkan sebagai bilangan prima sebelumnya dan berikutnya bagi dirinya sendiri, dan itu pilihan yang disengaja atas selang yang inklusif dan bukan dua baris yang gagal menemukan apa pun.

Apakah 1 bilangan prima?

Bukan, dan ia juga bukan bilangan komposit. Bilangan prima didefinisikan sebagai bilangan bulat yang lebih besar daripada 1 dengan tepat dua pembagi positif, sedangkan 1 hanya punya satu pembagi, sehingga ia gagal memenuhi definisinya pada kedua hitungan sekaligus. Ini pilihan yang dibuat dengan sengaja dan bukan kelalaian: kalau 1 dihitung sebagai bilangan prima, pernyataan bahwa setiap bilangan punya tepat satu faktorisasi prima tidak lagi benar, karena Anda bisa mengalikan sebuah faktorisasi dengan 1 sebanyak yang Anda suka. Mengeluarkan 1 itulah yang menjaga teorema itu tetap bersih. Karena ini soal definisi dan bukan soal aritmetika, halaman ini tidak menerima 1 sebagai masukan — jawabannya tinggal di sini.

Mengapa bilangan prima sebelumnya dan berikutnya keduanya kembali sebagai bilangan itu sendiri?

Karena kedua pencariannya inklusif. Bilangan prima sebelumnya adalah bilangan prima terbesar yang tidak lebih besar daripada bilangan Anda, dan bilangan prima berikutnya adalah bilangan prima terkecil yang tidak lebih kecil daripadanya. Ketika bilangannya sudah prima, ia memenuhi kedua keterangan itu, sehingga kedua barisnya melaporkan bilangan itu. Pilihan lainnya adalah pertidaksamaan yang ketat, dan dengan itu masukan berupa bilangan prima akan meninggalkan dua baris tanpa isi. Baris kosong pada panel hasil terbaca sebagai sesuatu yang sedang rusak, dan halaman ini justru tidak akan bisa menjawab kasus yang paling diyakininya. Kesepakatan yang sama muncul pada pembulatan, ketika bilangan yang sudah berada pada ketelitian yang dituju kembali tanpa berubah.

Mengapa bilangan prima berikutnya bisa lebih besar daripada satu juta sedangkan masukannya tidak boleh?

Karena batas atas itu membatasi apa yang boleh Anda tanyakan, dan bukan apa yang boleh menjadi jawabannya. Bilangan prima setelah 1.000.000 adalah 1.000.003, dan menolak mencetaknya berarti menolak menjawab pertanyaan yang dirumuskan dengan sempurna tentang masukan yang diterima halaman ini. Jadi pencarian tetangganya berjalan dengan ujiannya sendiri, tanpa batas atas, sementara jumlah pembaginya tetap memakai rutin bersama yang hanya mencakup rentang itu. Itu berarti ada dua logika yang keduanya memutuskan apakah sebuah bilangan prima — satu terbatas, satu tidak — dan keduanya wajib sepakat di mana pun keduanya bertumpang tindih, dan itulah yang diperiksa contoh 97: hitungannya berkata 2, dan pencarian tetangganya berkata 97 prima.

Bilangan prima sebenarnya dipakai untuk apa?

Terutama untuk menentukan ukuran. Tabel hash biasanya diberi jumlah slot berupa bilangan prima, karena modulus yang prima menyebarkan kunci-kunci yang punya faktor sama — tabel dengan 1.000 slot mengirim setiap kelipatan 25 ke beberapa posisi yang sama, sedangkan tabel dengan 997 slot tidak. Penalaran yang sama berlaku di mana pun sebuah penghitung berputar kembali: panjang siklus yang prima menghindari beresonansi dengan pola teratur di dalam datanya. Kriptografi adalah pemakaian besar yang lain, ketika kunci dibangun dari bilangan prima yang sangat besar dan berjauhan, dan keamanannya bersandar pada sulitnya memfaktorkan hasil kalinya kembali menjadi kedua bilangan prima asalnya. Pemakaian yang lebih kecil ada di mana-mana: memeriksa klaim keterbagian, menguji apakah sebuah bilangan merupakan hasil kali dua bilangan prima, dan teka-teki klasik tentang bilangan prima kembar serta jarak di antara bilangan prima yang berurutan.

Bagaimana halaman ini memutuskan, dan seberapa pasti keputusannya?

Dengan menghitung pembagi, dan itu tepat dan bukan berdasarkan peluang. Sebuah bilangan prima jika dan hanya jika ia punya tepat dua pembagi positif, sehingga hitungannya memutuskan pertanyaan itu tanpa kemungkinan jawaban yang salah, dan tanpa perlu mempercayai ujian yang bisa tertipu. Penghitungannya dilakukan dengan pembagian percobaan sampai akar kuadratnya, dan itulah sebabnya satu juta menjadi batas atasnya: di atas itu caranya menjadi lambat dan bukan menjadi tidak dapat dipercaya. Untuk bilangan yang jauh lebih besar, cara yang tepat memang benar-benar tidak praktis dan ujian berdasarkan peluang yang dipakai, tetapi pada ukuran ini tidak ada alasan untuk menerima apa pun yang kurang daripada kepastian, dan halaman ini tidak menerimanya.

Mengapa jumlah pembagi ditampilkan dan bukan hanya putusannya?

Karena hitungan itulah alasan putusannya, dan menampilkannya membuat keduanya tidak mungkin berselisih — lencananya bukan perhitungan kedua melainkan pembacaan atas angka yang dicetak di sebelahnya. Hitungan itu juga berguna tersendiri. Hitungan yang ganjil berarti bilangannya kuadrat sempurna, karena akar kuadratnya berpasangan dengan dirinya sendiri dan bukan dengan pembagi yang berbeda. Hitungan 2 adalah definisi bilangan prima. Hitungan yang besar dibandingkan ukuran bilangannya menandakan banyak faktor kecil, dan itulah jenis bilangan yang cepat mengumpulkan pembagi. Dan ia menghubungkan halaman ini dengan halaman-halaman lain: halaman faktorisasi prima melaporkan jumlah pembagi yang sama untuk masukan yang sama, dengan menghitungnya dari eksponennya, sehingga kedua halaman itu saling memeriksa.

• Prime Number — the definition, the divisor-count test, and why 1 is excluded by it — Wolfram MathWorld (United States)
• Prime Gaps — the distances between consecutive primes, and what the neighbourhood of a million looks like — Wolfram MathWorld (United States)
• Composite Number — the complement of the primes, and why 1 belongs to neither group — Wolfram MathWorld (United States)