Bagaimanakah Kita Boleh Mengoptimumkan Penapis Eratosthenes untuk Penjanaan Nombor Perdana yang Cekap dalam Python?

Sieve of Eratosthenes: Mengoptimumkan Penjanaan Nombor Perdana dalam Python

Sieve of Eratosthenes ialah algoritma klasik untuk mencari nombor perdana. Walau bagaimanapun, adalah penting untuk melaksanakannya dengan betul untuk mengelakkan kesesakan prestasi.

Pelaksanaan Asal

Fungsi primes_sieve yang disediakan mengekalkan senarai nombor perdana calon dan secara berulang mengalih keluar bukan- nombor perdana dengan merentasi senarai dan menghapuskan faktor. Pendekatan ini sememangnya tidak cekap kerana kos manipulasi senarai yang tinggi.

Pengoptimuman Berasaskan Kamus

Fungsi primes_sieve1 yang dipertingkatkan menggunakan kamus untuk menyimpan bendera primaliti. Walaupun lebih pantas daripada pendekatan berasaskan senarai, ia masih menghadapi cabaran. Ia berulang ke atas kamus dalam susunan yang tidak ditentukan, menyebabkan penandaan berlebihan bagi faktor bukan perdana. Di samping itu, ia menukar kamus akhir kepada senarai, menimbulkan overhed yang tidak perlu.

Pelaksanaan yang Betul dan Cekap

Algoritma Ayak Eratosthenes yang betul menggunakan senarai bendera boolean untuk menunjukkan keutamaan. Fungsi primes_sieve2 memulakan bendera kepada Benar untuk semua nombor dan menetapkan bendera untuk 0 dan 1 kepada Salah. Ia berulang melalui senarai, menandakan bukan bilangan prima dengan menetapkan benderanya kepada Palsu.

Pendekatan ini cekap kerana:

• Ia menggunakan senarai dan bukannya kamus, mengelakkan overhed operasi nilai kunci.
• Ia menandakan hanya faktor utama sebagai bukan perdana, mengurangkan lebihan operasi.
• Ia mengoptimumkan proses penandaan dengan bermula pada segi empat sama setiap perdana dan bukannya gandaannya.

Dengan melaksanakan Ayak Eratosthenes dengan betul, anda boleh meningkatkan prestasi dengan ketara penjanaan nombor perdana, menjadikannya sesuai walaupun untuk had input yang besar seperti mencari nombor perdana di bawah 2 juta.

Atas ialah kandungan terperinci Bagaimanakah Kita Boleh Mengoptimumkan Penapis Eratosthenes untuk Penjanaan Nombor Perdana yang Cekap dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!