0Pricing
Coding Interview Prep · Pelajaran

Saringan Eratosthenes

Mencantumkan semua bilangan prima hingga N dalam waktu hampir linear

Saringan Eratosthenes adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 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 Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Bilangan Prima dalam Jumlah Besar

Terkadang Anda memerlukan semua bilangan prima hingga N, bukan hanya satu pengujian. Saringan Eratosthenes menemukan semuanya dalam satu penyapuan. 🧹

Gagasan Utama

Mulailah dengan menganggap setiap bilangan sebagai bilangan prima. Kemudian coret kelipatan dari setiap bilangan prima yang Anda temukan, sehingga hanya bilangan prima sejati yang tersisa.

Siapkan Penanda

Buat daftar boolean dengan indeks i yang menandai apakah i merupakan bilangan prima. Larik ini adalah kanvas tempat saringan bekerja.

is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False

Telusuri Kandidat

Telusuri i ke arah yang lebih besar. Saat pertama kali menemukan bilangan yang masih ditandai True, bilangan itu pasti merupakan bilangan prima baru yang tidak memiliki faktor lebih kecil.

Coret Kelipatan

Untuk setiap bilangan prima i, tandai 2i, 3i, 4i, dan seterusnya sebagai bukan bilangan prima. Kelipatan tersebut jelas memiliki i sebagai pembagi.

for j in range(i * i, n + 1, i):
    is_prime[j] = False

Mulai dari i Kuadrat

Mulailah mencoret dari i*i, bukan 2i. Setiap kelipatan yang lebih kecil sudah dihapus oleh bilangan prima sebelumnya, jadi lewati semuanya.

Berhenti di Akar

Anda hanya perlu menjalankan saringan selama i*i tetap kurang dari atau sama dengan N. Setelah akar kuadrat, setiap penanda True yang tersisa sudah menunjukkan bilangan prima.

Saringan Lengkap

Gabungkan pemindaian luar dan pencoretan bagian dalam. Setelah perulangan selesai, setiap indeks yang masih ditandai True adalah bilangan prima yang telah dikonfirmasi.

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] = False

Kumpulkan Bilangan Prima

Baca penanda yang telah selesai ke dalam sebuah daftar menggunakan konstruksi pemahaman daftar. Sekarang Anda memiliki setiap bilangan prima hingga N yang siap digunakan untuk kueri cepat.

primes = [i for i, p in enumerate(is_prime) if p]

Mengapa Cepat

Saringan berjalan dalam waktu sekitar O(n log log n), hampir linear. Itulah sebabnya metode ini jauh mengungguli pengujian satu bilangan yang dilakukan berulang kali.

Perhatikan Penggunaan Memori

Larik penanda menggunakan memori yang sebanding dengan N. Untuk batas yang sangat besar, perhatikan anggaran ruang Anda sebelum melakukan alokasi.

Pemeriksaan Cepat

Ingat kembali pengoptimalan kecil dalam perulangan bagian dalam.

Ringkasan

Sekarang Anda dapat membuat saringan untuk mencantumkan semua bilangan prima hingga N dalam waktu yang hampir linear, memulai setiap bilangan prima dari i*i dan berhenti di akar. ✅

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Saringan Eratosthenes” gratis?

Ya — teks lengkap “Saringan Eratosthenes” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Saringan Eratosthenes”?

Mencantumkan semua bilangan prima hingga N dalam waktu hampir linear Kamu berlatih Coding Interview Prep 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 Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep 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 3 dari 4.

Berapa lama pelajaran “Saringan Eratosthenes” 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 Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep 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

  1. GCD, LCM & Algoritma Euclid
  2. Pengujian Keprimaan hingga sqrt(n)
  3. Saringan Eratosthenes
  4. Faktorisasi Prima & Pembagi
← Kembali ke Coding Interview Prep