Faktorisasi prima
Uraikan bilangan bulat menjadi faktor-faktor primanya, daftarkan pembaginya, dan periksa apakah bilangan itu prima.
Berjalan sepenuhnya di browser Anda. Tidak ada yang diunggah, dicatat, atau disimpan.
Faktorisasi prima
2^3 × 3^2 × 5
- Prima?
- tidak
- Faktor prima yang berbeda
- 3
- Jumlah pembagi
- 24
- Pembagi
- 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
Setiap bilangan bulat yang lebih besar dari 1 adalah hasil kali bilangan prima, dan hanya ada satu hasil kali seperti itu untuknya: itulah teorema dasar aritmetika. Alat ini menemukannya, beserta semua yang mengikutinya: berapa banyak pembagi bilangan itu dan apa saja.
Cara kerja
Pembagian coba-coba, dengan satu jalan pintas: setelah 2 dan 3 dikeluarkan, semua bilangan prima yang tersisa berada tepat di sebelah kiri atau kanan kelipatan enam, jadi kandidatnya maju enam demi enam, bukan dua demi dua. Apa pun yang lolos dari saringan adalah prima dan masuk sebagai faktor terakhir.
Pembagi disusun dari faktorisasi, bukan dengan mencoba semua bilangan sampai n. Bilangan yang ditulis sebagai 2³ × 3² × 5 memiliki (3+1) × (2+1) × (1+1) = 24 pembagi, dan masing-masing adalah pilihan berapa banyak tiap bilangan prima diambil, jadi mendaftarnya tidak memakan biaya begitu faktorisasinya diketahui.
Batasnya satu triliun. Pembagian coba-coba paling jauh berjalan sampai akar kuadrat bilangan itu, yang di sana berarti sejuta langkah: cepat. Di atas itu, bilangan yang ternyata hasil kali dua bilangan prima besar akan membuat halaman terus memuat selama semenit, jadi halaman ini menolak.
Contoh
| Kasus | Masukan | Hasil |
|---|---|---|
| Bilangan dengan banyak pembagi | 360 | 2³ × 3² × 5: 24 pembagi |
| Bilangan prima | 97 | 97: prima, 2 pembagi |
| Pangkat dua | 1024 | 2¹⁰: 11 pembagi |
Pertanyaan umum
Mengapa dimulai dari 2, bukan 1?
Karena 1 tidak memiliki faktorisasi prima, dan menyebutnya prima akan merusak keunikan yang menjadi dasar seluruh pokok bahasan ini: jika 1 prima, 6 akan menjadi 2 × 3, dan 1 × 2 × 3, dan 1 × 1 × 2 × 3, dan tidak ada lagi satu jawaban. Nol lebih buruk lagi: setiap bilangan membaginya.
Berapa banyak pembagi sebuah bilangan?
Tambahkan satu pada setiap eksponen dalam faktorisasi, lalu kalikan. 360 adalah 2³ × 3² × 5, jadi 4 × 3 × 2 = 24. Bilangan prima memiliki 2 — dirinya sendiri dan 1 — dan bilangan kuadrat sempurna selalu memiliki jumlah pembagi ganjil, karena salah satu pembaginya berpasangan dengan dirinya sendiri.
Mengapa ada batas atas?
Pembagian coba-coba eksak dan cepat, sampai tidak lagi cepat. Kasus terburuknya adalah hasil kali dua bilangan prima yang dekat dengan akar kuadrat, dan batas di sini ada di titik ketika kasus itu masih selesai dalam satu kali muat halaman. Penolakan memberi tahu Anda apa yang terjadi; waktu habis tidak memberi tahu apa-apa.
Apakah begini cara kunci enkripsi dibobol?
Tidak, dan justru di situ intinya. RSA bergantung pada sulitnya memfaktorkan bilangan yang panjangnya beberapa ratus digit; pembagian coba-coba pada bilangan seperti itu akan berlangsung lebih lama dari umur alam semesta. Metode yang lebih baik memang ada dan tetap jauh dari mampu, itulah sebabnya skema ini berfungsi.
Perlu diketahui
- Pembagi didaftar lengkap hingga enam puluh empat; lebih dari itu hanya jumlahnya yang ditampilkan, karena halaman berisi sembilan ratus angka bukan sesuatu yang akan dibaca orang.