Pemeriksa Bilangan Prima

Cara menggunakan pemeriksa bilangan prima

1. Ketik sebuah Bilangan bulat. Ekspresi juga diterima: 2^61-1, 10^12+39, 20!+1, atau 3711.
2. Jawabannya muncul saat Anda mengetik; tekan Periksa untuk memberi waktu lebih lama pada faktorisasi bilangan yang sulit.
3. Baca hasil penilaiannya, Faktorisasi prima, Jumlah pembagi, Bilangan prima sebelumnya, dan Bilangan prima berikutnya. Panel Alasan menjelaskan bagaimana jawaban diperoleh, dan Salin faktorisasi menyalin hasil kali bilangan prima.
4. Untuk menampilkan daftar bilangan prima, isi Dari dan Sampai di bawah Bilangan prima dalam rentang, lalu tekan Tampilkan bilangan prima.

Bilangan hingga 2048 bit (sekitar 617 digit) diterima, dan semuanya berjalan di browser Anda.

Apa yang membuat bilangan menjadi prima

Bilangan prima adalah bilangan bulat lebih besar dari 1 yang hanya habis dibagi 1 dan dirinya sendiri: 2, 3, 5, 7, 11, 13, dan seterusnya. Bilangan yang memiliki pembagi lain disebut komposit, dan dapat ditulis dengan tepat satu cara sebagai hasil kali bilangan prima, yaitu faktorisasi prima-nya (360 = 2³ × 3² × 5). Bilangan 0 dan 1 bukan prima dan bukan komposit, dan 2 adalah satu-satunya bilangan prima genap.

Jumlah pembagi dapat diturunkan dari faktorisasi: tambahkan 1 pada setiap eksponen lalu kalikan. 360 = 2³ × 3² × 5 memiliki (3 + 1)(2 + 1)(1 + 1) = 24 pembagi. Bilangan prima selalu memiliki tepat 2 pembagi.

Cara kerja pengujian

• Bilangan kecil (di bawah satu juta) diperiksa dengan pembagian percobaan: jika tidak ada bilangan prima sampai akar kuadratnya yang membagi bilangan itu, maka bilangan tersebut prima. Tidak perlu memeriksa lebih jauh, karena bilangan komposit selalu memiliki faktor yang tidak lebih besar dari akar kuadratnya.
• Bilangan yang lebih besar pertama-tama dibagi dengan setiap bilangan prima di bawah 1000, lalu diuji dengan tes Miller–Rabin. Dengan 13 basis 2, 3, 5, …, 41, tes ini terbukti eksak untuk setiap bilangan di bawah 3,3 × 10²⁴, termasuk semua bilangan bulat 64 bit. Untuk bilangan-bilangan itu jawabannya pasti.
• Di atas 3,3 × 10²⁴, dipakai 25 basis dan bilangan yang lolos semuanya dilaporkan sebagai kemungkinan besar prima. Peluang kesalahannya di bawah 1 banding 10¹⁵, tetapi itu bukan bukti matematis. Jika tes gagal, bilangan itu pasti komposit.

Cara bilangan difaktorkan

Faktor kecil ditemukan dengan pembagian percobaan. Bagian komposit yang lebih besar dipecah dengan algoritma rho Pollard (varian Brent), yang menemukan faktor hingga sekitar 10 digit dalam sekejap. Bilangan yang lebih sulit, seperti hasil kali dua bilangan prima berdigit 15 atau lebih, bisa memakan waktu jauh lebih lama dari batas waktu mana pun, sehingga pemfaktoran berhenti setelah beberapa detik. Faktor terakhir lalu ditandai sebagai komposit yang belum terpecah, dan menekan Periksa lagi akan memberinya waktu lebih lama.

Bilangan prima dalam rentang

Daftar rentang memakai saringan Eratosthenes bersegmen, yang mencoret kelipatan setiap bilangan prima. Rentang yang diterima maksimal 1.000.000 bilangan dengan batas atas sampai 10¹². Jumlahnya dihitung untuk seluruh rentang, dan 2.000 bilangan prima pertama ditampilkan. Misalnya, ada 25 bilangan prima antara 1 dan 100 serta 78.498 di bawah satu juta.