Faktorisasi Prima & Pembagi
Memecah N menjadi pangkat prima dan menghitung pembagi
Faktorisasi Prima & Pembagi adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Uraikan N
Setiap bilangan bulat di atas 1 merupakan hasil kali unik dari bilangan-bilangan prima. Menemukan uraian tersebut, yaitu faktorisasi prima, membuka jalan untuk menyelesaikan banyak masalah teori bilangan. 🧩
Gagasan Pembagian Percobaan
Ambil bilangan prima terkecil yang membagi n, bagikan n dengan bilangan tersebut, lalu ulangi. Pembagian percobaan sederhana ini menguraikan n hingga menjadi 1.
Berulang hingga Akar
Uji pembagi i selama i*i tetap kurang dari atau sama dengan n. Setelah akar kuadrat, paling banyak satu faktor prima yang masih tersisa.
while i * i <= n:
...Ambil Setiap Faktor
Selama i membagi n, terus lakukan pembagian dan catat i. Dengan demikian, seluruh pangkat bilangan prima tersebut tercatat sebelum Anda melanjutkan.
while n % i == 0:
factors.append(i)
n //= iBilangan Prima yang Tersisa
Setelah perulangan selesai, jika n masih lebih besar dari 1, n itu sendiri merupakan faktor prima yang lebih besar dari akar kuadrat. Tambahkan satu kali.
if n > 1:
factors.append(n)Rutinitas Lengkap
Secara keseluruhan, proses ini menghasilkan faktorisasi dalam waktu O(sqrt n), dengan mengembalikan setiap bilangan prima beserta multiplisitas penuhnya dalam urutan.
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return fKelompokkan menjadi Pangkat
Untuk menghitung pembagi, Anda memerlukan setiap bilangan prima beserta pangkatnya, seperti 2^3, bukan 2,2,2. Pencacah menghitung pengulangan dengan rapi.
from collections import Counter
exp = Counter(factorize(n))Rumus Pembagi
Jika n adalah p1^a dikalikan p2^b, jumlah pembagi adalah (a+1) dikalikan (b+1). Setiap pangkat mendapat satu pilihan tambahan.
Menghitung Pembagi
Kalikan satu ditambah setiap eksponen untuk semua bilangan prima. Dengan begitu, Anda mendapatkan jumlah seluruh pembagi tanpa perlu menuliskannya satu per satu.
count = 1
for e in exp.values():
count *= (e + 1)Jumlah Pembagi
Rumus terkait menjumlahkan pembagi menggunakan deret geometri dari setiap bilangan prima. Memahaminya membantu Anda menyelesaikan masalah bilangan sempurna dan jumlah pembagi sejati.
Mempercepat dengan Saringan
Untuk banyak faktorisasi, lakukan praperhitungan faktor prima terkecil dari setiap bilangan menggunakan saringan. Setelah itu, setiap kueri dapat difaktorkan dalam log n langkah.
Pemeriksaan Cepat
Terapkan rumus penghitungan pembagi pada sebuah bilangan konkret.
Ringkasan
Sekarang Anda dapat memfaktorkan N dengan pembagian percobaan dalam O(sqrt n), menangani faktor prima yang tersisa, mengelompokkan eksponen, dan menghitung pembagi dengan rumus hasil kali. ✅
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Faktorisasi Prima & Pembagi” gratis?
Ya — teks lengkap “Faktorisasi Prima & Pembagi” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Faktorisasi Prima & Pembagi”?
Memecah N menjadi pangkat prima dan menghitung pembagi Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Faktorisasi Prima & Pembagi” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- GCD, LCM & Algoritma Euclid
- Pengujian Keprimaan hingga sqrt(n)
- Saringan Eratosthenes
- Faktorisasi Prima & Pembagi