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

Ayak Eratosthenes Diperbaiki: Mengoptimumkan Penjanaan Perdana Python

Ayak Eratosthenes ialah algoritma yang cekap untuk mencari nombor perdana sehingga had yang telah ditetapkan . Walau bagaimanapun, pelaksanaan Python yang naif boleh menjadi terlalu perlahan untuk had yang lebih besar.

Mengenalpasti Bottlenecks

Dalam contoh yang diberikan, pemprofilan mendedahkan bahawa masa yang ketara telah digunakan untuk mengalih keluar elemen daripada senarai (bilangan perdana). Operasi ini adalah mahal dari segi pengiraan, terutamanya untuk senarai panjang.

Menggantikan Senarai dengan Kamus

Percubaan awal untuk menangani isu ini melibatkan menggantikan senarai dengan kamus (bilangan nombor) . Ini membolehkan penyingkiran unsur yang lebih cepat. Walau bagaimanapun, algoritma masih mengalami:

• Lelaran ke atas kamus dalam susunan yang tidak ditentukan
• Penandaan berlebihan bagi faktor nombor bukan perdana

Melaksanakan Algoritma yang Betul

Untuk mengoptimumkan sepenuhnya algoritma, pembetulan diperlukan:

1. Menggunakan senarai dan bukannya kamus untuk bendera keutamaan
2. Melangkau faktor bukan perdana
3. Memulakan penandaan faktor pada titik perdana segi empat sama, bukannya dua kali ganda

Yang Dioptimumkan Algoritma

Algoritma yang dioptimumkan (primes_sieve2) menggunakan senarai boolean untuk bendera primaliti. Ia memulakan senarai kepada Benar untuk semua nombor yang lebih besar daripada 1. Kemudian, ia berulang melalui senarai, menandakan nombor bukan perdana:

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    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

Dengan mengoptimumkan aspek utama ini, algoritma meningkatkan prestasinya dengan ketara, mencari nombor perdana sehingga 2 juta dalam masa beberapa saat.

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