Periksa apakah sebuah bilangan bulat merupakan bilangan prima, dan lihat pembagi terkecilnya bila bukan.
Contoh
97 adalah bilangan prima, begitu pula 7.919, yaitu prima ke-1.000. 91 bukan prima karena 91 = 7 × 13, dan 221 habis dibagi 13 sebab 221 = 13 × 17.
Metode perhitungan
Pemeriksa menangani 2 dan bilangan genap terlebih dahulu, lalu mencoba pembagi ganjil sampai akar kuadrat bilangan yang Anda masukkan. Jika ada faktor di atas titik itu, pasangannya pasti lebih kecil dan sudah ditemukan lebih dulu. Bahkan 999.999.937, prima terbesar di bawah satu miliar, hanya butuh sekitar 15.800 pembagian percobaan, sehingga jawabannya muncul hampir seketika.
Catatan penting
Masukkan bilangan bulat dari 2 sampai 1.000.000.000. Angka 1 bukan bilangan prima, karena prima memiliki tepat dua pembagi positif, dan desimal ditolak sebab keprimaan berlaku untuk bilangan bulat. Bila bilangannya komposit, hasilnya menyebutkan pembagi terkecil yang lebih besar dari 1.
Pertanyaan umum
Mengapa bilangan yang tampak prima ternyata bukan?
Faktor kecil mudah tersembunyi. 561 adalah bilangan Carmichael terkecil yang lolos beberapa uji probabilistik cepat, padahal habis dibagi 3. Penjumlahan digitnya membongkar itu: 5 + 6 + 1 = 12, yang habis dibagi 3. Alat ini menguji pembagi secara langsung, jadi jawabannya pasti.
Mengapa pengujian berhenti di akar kuadrat?
Karena faktor selalu berpasangan. Untuk 221, pencarian berhenti begitu mencapai 13, sebab 221 = 13 × 17 dan faktor yang lebih besar pasti sudah berpasangan dengan yang lebih kecil. Inilah yang membuat pemeriksaan tetap cepat bahkan untuk bilangan mendekati satu miliar.
Bisakah dipakai untuk kriptografi?
Tidak. Alat ini dibuat untuk belajar dan pemeriksaan sehari-hari hingga 1.000.000.000. Bilangan prima untuk enkripsi panjangnya ratusan digit dan dihasilkan dengan uji probabilistik serta bilangan acak yang aman, sesuatu yang tidak bisa dicapai pembagian percobaan dalam waktu wajar.