Pemeriksa Bilangan Prima (dengan faktorisasi)
Masukkan bilangan bulat non-negatif hingga 10^18. Kalkulator menguji primitas dengan pembagian percobaan (deterministik hingga ~10^15 dalam waktu yang wajar) dan memberikan faktorisasi prima untuk bilangan komposit.
- Prima sebelumnya
- 89
- Prima berikutnya
- 101
Cara kerjanya
Apa itu bilangan prima
Prima adalah bilangan asli lebih dari 1 yang tidak memiliki pembagi positif selain 1 dan dirinya sendiri. Beberapa prima pertama: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. Mereka adalah 'atom' aritmetika bilangan bulat โ setiap bilangan bulat โฅ 2 dapat ditulis secara unik sebagai hasil kali bilangan prima (Teorema Dasar Aritmetika).
1 bukan prima menurut konvensi. 0 dan bilangan negatif bukan prima. 2 adalah satu-satunya prima genap โ setiap bilangan genap lainnya habis dibagi 2 dan karenanya komposit.
Cara pengujian bekerja
Kami menggunakan pembagian percobaan: periksa keterbagian dengan 2, lalu 3, lalu 5, 7, 11, โฆ hingga โn. Jika tidak ada yang membagi dengan bersih, n adalah prima. Kami menggunakan optimasi 6kยฑ1 yang hanya memeriksa kandidat berbentuk 6k+1 atau 6kโ1 (karena semua prima > 3 berbentuk ini), mengurangi jumlah pengujian sebesar 2/3.
Pembagian percobaan cepat untuk n hingga ~10^15 (di bawah satu detik). Di atasnya, pengujian lanjutan seperti Miller-Rabin (probabilistik) atau AKS (deterministik) diperlukan. Kami membatasi di 10^18 untuk mencegah browser membeku pada input ekstrem.
Mengapa bilangan prima penting
Kriptografi: enkripsi RSA mengalikan dua prima berdigit ~1000 untuk menghasilkan bilangan yang sulit difaktorkan. Keamanannya bergantung pada sulitnya memfaktorkan bilangan besar โ tantangan yang telah dipelajari selama ribuan tahun.
Pendidikan matematika: faktorisasi prima adalah fondasi. Konsep seperti FPB, KPK, aritmetika modular, pecahan, dan teori bilangan semuanya dibangun di atas struktur faktor prima.
Ilmu komputer: ukuran tabel hash, generator bilangan acak, dan banyak algoritma menggunakan prima karena sifat keterbagiannya yang khas.
Pertanyaan umum
โบApakah 1 prima?
Tidak. 1 adalah 'satuan', bukan prima. Prima memiliki tepat dua pembagi positif berbeda (1 dan dirinya sendiri); 1 hanya memiliki satu.
โบApakah 0 prima?
Tidak. Prima adalah bilangan bulat > 1.
โบApakah 2 prima?
Ya โ 2 adalah satu-satunya prima genap. Semua bilangan genap lainnya memiliki 2 sebagai pembagi selain 1 dan dirinya sendiri.
โบBagaimana prima berikutnya ditemukan?
Dengan menambah dari n+1 dan menguji primitas di setiap langkah. Selalu ada prima dalam n ร ln(n) dari bilangan mana pun, sehingga ini berakhir dengan cepat bahkan untuk input besar.
โบMengapa maksimumnya 10^18?
JavaScript BigInt menangani yang lebih besar, tetapi pembagian percobaan menjadi lambat. 10^18 aman untuk pemeriksaan di bawah satu detik untuk input khas. Lebih dari itu, gunakan alat khusus seperti SymPy atau Mathematica.
โบBisakah Anda memeriksa prima 1000 digit?
Tidak dengan alat ini โ pembagian percobaan terlalu lambat pada skala itu. Kriptografi menggunakan pengujian probabilistik Miller-Rabin untuk prima 1024-bit (~300 digit).
โบApa itu prima Mersenne?
Prima berbentuk 2^p โ 1. Hingga 2025, hanya 51 yang diketahui. Prima terbesar yang diketahui (M82589933) adalah prima Mersenne dengan ~25 juta digit.
โบApakah data meninggalkan browser saya?
Tidak. Perhitungan berjalan secara lokal; tidak ada yang dikirim ke server.
Alat terkait
Terakhir diperbarui: