Apakah Cara Terpantas untuk Mencari Semua Nombor Perdana Di Bawah Integer N Diberi?

Cara Terpantas untuk Menyenaraikan Semua Perdana Di Bawah N

Coretan kod ini memberikan pelaksanaan Python kaedah untuk menjana senarai nombor perdana dengan cekap sehingga integer tertentu.

    def get_primes(n):
        numbers = set(range(2, n + 1))
        primes = []
        while numbers:
            p = numbers.pop()
            primes.append(p)
            numbers.difference_update(set(range(p * p, n + 1, p)))
        return primes

Masa Kerumitan:

Kerumitan masa kod yang diberikan ialah O(n log log n), kerana ia menggunakan Sieve of Eratosthenes untuk mengira nombor perdana.

Nota Pelaksanaan :

• Kod ini memulakan set nombor yang mengandungi semua integer dari 2 hingga n.
• Ia secara berulang mengalih keluar nombor bukan perdana daripada nombor dengan menandakan sebagai komposit semua gandaan nombor terkecil yang masih belum ditanda. Gandaan ini dilangkau dengan mengambil langkah daripada nombor perdana semasa semasa mengemas kini nombor.
• Kod berhenti apabila nombor kosong dan senarai nombor perdana yang ditemui dikembalikan dalam nombor perdana.

Isu Potensi:

Terdapat isu yang berpotensi dengan pelaksanaan di mana ia menandakan nombor permulaan sebagai nombor perdana apabila ia hanya perlu mempertimbangkan nombor dari 2 hingga n. Ini boleh dibetulkan dengan memulakan gelung daripada 2 dan bukannya 0.

Penggunaan:

Untuk menggunakan pelaksanaan ini, anda boleh memanggil fungsi get_primes dan lulus bahagian atas yang dikehendaki terikat sebagai hujah. Contohnya, untuk mencari semua nombor perdana sehingga 1000, anda boleh menggunakan:

primes = get_primes(1000)

Output:

Output kod akan menjadi senarai perdana nombor sehingga integer yang ditentukan. Sebagai contoh, menjalankan kod dengan n = 1000 akan menghasilkan output berikut:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ..., 977]

Atas ialah kandungan terperinci Apakah Cara Terpantas untuk Mencari Semua Nombor Perdana Di Bawah Integer N Diberi?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!