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

Mengoptimumkan Penjanaan Nombor Perdana dengan Ayak Eratosthenes dalam Python

Ayak Eratosthenes ialah algoritma berperingkat masa untuk mengenal pasti nombor perdana sehingga had yang ditentukan. Walaupun mudah untuk dilaksanakan, ia boleh menghairankan lambat untuk had yang besar.

Pelaksanaan Lambat

Pelaksanaan Python berikut bagi ayak menghadapi cabaran dengan kecekapan:

def primes_sieve(limit):
    primes = range(2, limit+1)

    for i in primes:
        factors = range(i, limitn, i)
        for f in factors[1:]:
            if f in primes:
                primes.remove(f)

Hambatan terletak pada saiz semula senarai perdana secara berterusan apabila nombor dialih keluar. Mengalih keluar item daripada senarai Python melibatkan peralihan elemen seterusnya, menjadikannya operasi yang mahal dari segi pengiraan.

Pelaksanaan Lebih Pantas Menggunakan Kamus

Untuk menangani perkara ini, pelaksanaan berasaskan kamus boleh digunakan:

def primes_sieve1(limit):
    primes = dict()
    for i in range(2, limit+1): primes[i] = True

    for i in primes:
        factors = range(i,limitn, i)
        for f in factors[1:]:
            primes[f] = False

Ini mengekalkan kamus bendera keutamaan, mengurangkan keperluan untuk mengubah saiz operasi. Walau bagaimanapun, mengulangi kekunci kamus dalam susunan yang tidak ditentukan dan menandakan berulang kali faktor bukan perdana bagi nombor bukan perdana mengehadkan kecekapan.

Algoritma Dibetulkan dengan Senarai

Pelaksanaan yang betul mengikuti algoritma Sieve of Eratosthenes dengan lebih dekat:

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

Ini mengekalkan senarai bendera primaliti, memulakan semua nombor sebagai perdana kecuali 0 dan 1. Ia menandakan gandaan nombor perdana sebagai bukan perdana, bermula pada kuasa dua perdana untuk mengoptimumkan proses.

Dengan menangani isu kecekapan dalam pelaksanaan, algoritma yang diperbetulkan ini meningkatkan dengan ketara kelajuan penjanaan nombor perdana, walaupun untuk had yang besar.

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