Pemfaktoran Perdana dan Pembahagi
Pecahkan N kepada kuasa perdana dan kira pembahagi.
Pemfaktoran Perdana dan Pembahagi ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Pecahkan N
Setiap integer yang lebih besar daripada 1 ialah hasil darab unik nombor perdana. Mencari pecahan itu, iaitu pemfaktoran perdana, membuka jalan kepada banyak masalah teori nombor. 🧩
Idea Pembahagian Percubaan
Keluarkan nombor perdana terkecil yang membahagi n, bahagikan n dengannya, dan ulangi. Pembahagian percubaan yang ringkas ini mengurangkan n sehingga menjadi 1.
Ulang Gelung hingga Punca Kuasa Dua
Uji pembahagi i selagi i*i kurang daripada atau sama dengan n. Selepas punca kuasa dua, paling banyak satu faktor perdana boleh tinggal.
while i * i <= n:
...Ekstrak Setiap Faktor
Selagi i membahagi n, teruskan pembahagian dan rekodkan i. Ini menangkap kuasa penuh nombor perdana itu sebelum anda bergerak ke faktor seterusnya.
while n % i == 0:
factors.append(i)
n //= iFaktor Perdana yang Tertinggal
Selepas gelung tamat, jika n masih lebih besar daripada 1, n sendiri ialah faktor perdana yang lebih besar daripada punca kuasa dua. Tambahkannya sekali.
if n > 1:
factors.append(n)Rutin Penuh
Secara keseluruhannya, pemfaktoran ini mengambil masa O(sqrt n) dan mengembalikan setiap nombor perdana bersama gandaan penuhnya mengikut turutan.
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 fKumpulkan kepada Kuasa
Untuk mengira pembahagi, anda mahu setiap nombor perdana bersama eksponennya, seperti 2^3 dan bukannya 2,2,2. Satu Counter mengira pengulangan dengan kemas.
from collections import Counter
exp = Counter(factorize(n))Formula Pembahagi
Jika n ialah p1^a didarab dengan p2^b, bilangan pembahagi ialah (a+1) didarab dengan (b+1). Setiap eksponen mendapat satu pilihan tambahan.
Kira Pembahagi
Darabkan satu ditambah setiap eksponen bagi semua nombor perdana. Ini memberikan jumlah kiraan pembahagi tanpa perlu menyenaraikannya.
count = 1
for e in exp.values():
count *= (e + 1)Jumlah Pembahagi
Formula berkaitan menjumlahkan pembahagi menggunakan siri geometri bagi setiap nombor perdana. Mengetahuinya membantu menyelesaikan masalah nombor sempurna dan aliquot.
Percepat dengan Saringan
Untuk banyak pemfaktoran, kira terlebih dahulu faktor perdana terkecil bagi setiap nombor menggunakan saringan. Kemudian, setiap pertanyaan boleh difaktorkan dalam langkah log n.
Semakan Pantas
Terapkan formula pengiraan pembahagi pada nombor tertentu.
Rumusan
Sekarang Anda boleh memfaktorkan N melalui pembahagian percubaan dalam O(sqrt n), mengambil kira faktor perdana yang berbaki, mengumpulkan eksponen dan mengira pembahagi menggunakan formula hasil darab. ✅
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Pemfaktoran Perdana dan Pembahagi” percuma?
Ya — teks penuh “Pemfaktoran Perdana dan Pembahagi” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Pemfaktoran Perdana dan Pembahagi”?
Pecahkan N kepada kuasa perdana dan kira pembahagi. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Pemfaktoran Perdana dan Pembahagi” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- GCD, LCM dan Algoritma Euclid
- Pengujian Keprimaan hingga sqrt(n)
- Saringan Eratosthenes
- Pemfaktoran Perdana dan Pembahagi