Saringan Eratosthenes
Senaraikan semua nombor perdana hingga N dalam masa hampir linear.
Saringan Eratosthenes ialah pelajaran Competitive Programming Academy percuma di CoddyKit. Ini ialah pelajaran 3 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 Competitive Programming Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Nombor Perdana secara Pukal
Kadang-kadang anda memerlukan setiap nombor perdana sehingga N, bukan sekadar satu ujian. Saringan Eratosthenes mencarinya semua dalam satu imbasan. 🧹
Idea Utama
Mulakan dengan menganggap setiap nombor ialah perdana. Kemudian pangkah keluar gandaan bagi setiap nombor perdana yang anda temui, supaya hanya nombor perdana sebenar yang tinggal.
Sediakan Penanda
Cipta senarai nilai benar atau palsu, dengan indeks i menandakan sama ada i ialah nombor perdana. Tatasusunan ini ialah ruang kerja yang digunakan oleh penapis.
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = FalseTelusuri Calon
Gerakkan i ke arah yang lebih besar. Kali pertama anda mencapai nombor yang masih ditandakan True, nombor itu mestilah perdana baharu yang tiada faktor lebih kecil.
Pangkah Keluar Gandaan
Bagi setiap nombor perdana i, tandakan 2i, 3i, 4i dan seterusnya sebagai bukan perdana. Gandaan tersebut jelas mempunyai i sebagai pembahagi.
for j in range(i * i, n + 1, i):
is_prime[j] = FalseMulakan pada i Kuasa Dua
Mulakan proses memangkah pada i*i, bukan 2i. Setiap gandaan yang lebih kecil telah pun dibuang oleh nombor perdana terdahulu, jadi anda boleh melangkauinya.
Berhenti pada Punca Kuasa Dua
Anda hanya perlu menjalankan penapisan selagi i*i kurang daripada atau sama dengan N. Selepas punca kuasa dua itu, setiap penanda True yang masih tinggal sudah pun menandakan nombor perdana.
Penapis Penuh
Gabungkan imbasan luar dengan proses memangkah keluar di dalam. Selepas gelung tamat, setiap indeks yang masih ditandakan True ialah nombor perdana yang disahkan.
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = FalseKumpulkan Nombor Perdana
Baca penanda yang telah siap ke dalam satu senarai menggunakan kefahaman senarai. Kini anda mempunyai setiap nombor perdana sehingga N, sedia untuk pertanyaan pantas.
primes = [i for i, p in enumerate(is_prime) if p]Sebab Ia Pantas
Penapis berjalan dalam kira-kira O(n log log n), hampir linear. Itulah sebabnya ia mengatasi ujian satu nombor yang berulang kali.
Perhatikan Penggunaan Memori
Tatasusunan penanda menggunakan memori yang berkadar dengan N. Untuk had yang sangat besar, perhatikan bajet ruang anda sebelum memperuntukkan memori.
Semakan Pantas
Ingat pengoptimuman kecil dalam gelung dalaman.
Ringkasan
Anda kini boleh membina penapis untuk menyenaraikan semua nombor perdana sehingga N dalam masa yang hampir linear, bermula pada i*i bagi setiap nombor perdana dan berhenti pada punca kuasa dua. ✅
Pelajari Python 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
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “Saringan Eratosthenes” percuma?
Ya — teks penuh “Saringan Eratosthenes” 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 Competitive Programming Academy, tingkat taraf kepada CoddyKit PRO. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Saringan Eratosthenes”?
Senaraikan semua nombor perdana hingga N dalam masa hampir linear. Anda berlatih Competitive Programming Academy 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 Competitive Programming Academy?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Competitive Programming Academy 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 3 daripada 4.
Berapa lamakah pelajaran “Saringan Eratosthenes” 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 Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy 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