Bagaimana untuk Menjana Aliran Nombor Perdana Tak Terhingga dengan Cekap dalam Python?

Bagaimana untuk melaksanakan penjana nombor perdana tak terhingga yang cekap dalam Python?

Cara yang cekap untuk menjana siri nombor perdana tak terhingga adalah dengan menggunakan Sieve of Eratosthenes, yang menghapuskan nombor bukan perdana dengan menandakan secara berulang gandaannya. Walaupun kaedah ini berkesan, ia memerlukan banyak memori untuk menyimpan nombor yang ditanda.

erat2

Berikut ialah fungsi erat2 daripada buku masakan perpustakaan standard Python, yang boleh digunakan untuk menjana siri perdana tak terhingga nombor:

import itertools as it
def erat2( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

erat2a

Fungsi erat2 boleh dioptimumkan lagi dengan mengelakkan pemeriksaan yang tidak perlu:

import itertools as it
def erat2a( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

erat3

Untuk prestasi yang lebih pantas, fungsi erat3 memanfaatkan hakikat bahawa semua nombor perdana (kecuali 2, 3, dan 5) modulo 30 menghasilkan hanya lapan nombor tertentu. Ini mengurangkan dengan ketara bilangan semakan yang diperlukan semasa proses penyaringan:

import itertools as it
def erat3( ):
    D = { 9: 3, 25: 5 }
    yield 2
    yield 3
    yield 5
    MASK= 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0,
    MODULOS= frozenset( (1, 7, 11, 13, 17, 19, 23, 29) )

    for q in it.compress(
            it.islice(it.count(7), 0, None, 2),
            it.cycle(MASK)):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            x = q + 2*p
            while x in D or (x%30) not in MODULOS:
                x += 2*p
            D[x] = p

Pengoptimuman ini boleh menghasilkan peningkatan prestasi yang ketara, terutamanya apabila menjana nombor perdana yang besar.

Atas ialah kandungan terperinci Bagaimana untuk Menjana Aliran Nombor Perdana Tak Terhingga dengan Cekap dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!