Bagaimanakah Kita Boleh Mengoptimumkan Ayak Algoritma Eratosthenes dalam Python untuk Penjanaan Nombor Perdana yang Lebih Pantas?

Ayak Eratosthenes - Mencari Primes dalam Python

Masalah:

Semasa cuba melaksanakan algoritma Sieve of Eratosthenes dalam Python, pengguna sering menghadapi masa pelaksanaan yang perlahan, terutamanya semasa mencari untuk bilangan prima melebihi 1 juta.

Penyelesaian:

Pelaksanaan yang diberikan membentangkan beberapa bidang untuk penambahbaikan:

1. Algoritma Tidak Dioptimumkan:

• Pelaksanaan awal, primes_sieve, mengekalkan senarai prima, yang membawa kepada penyingkiran elemen yang tidak cekap.
• primes_sieve1 menggunakan kamus untuk bendera primaliti tetapi tidak mempunyai lelaran yang betul dan faktor berlebihan menanda.

2. Ketidakcekapan Manipulasi Senarai:

• Mengalih keluar elemen daripada senarai Python adalah operasi yang mahal kerana keperluan untuk mengalih elemen berikutnya.

Pelaksanaan Dioptimumkan :

Untuk menyelesaikan isu ini, pertimbangkan perkara berikut dioptimumkan pelaksanaan:

def primes_sieve2(limit):
    a = [True] * limit
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

Penambahbaikan Utama:

• Menggunakan senarai terus untuk bendera keutamaan, mengelakkan saiz semula senarai yang mahal.
• Malas menjana nombor perdana atas permintaan, menghapuskan keperluan untuk menyimpan penuh senarai.
• Menandai faktor bukan perdana dengan cekap dengan bermula di petak perdana.

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