Bagaimanakah Penapisan Algoritma Eratosthenes Boleh Dioptimumkan untuk Penjanaan Nombor Perdana yang Lebih Cepat?

Ayak Eratosthenes

Ayak Eratosthenes ialah algoritma purba, tetapi ia masih digunakan hari ini sebagai cara yang mudah dan cekap untuk mencari semua nombor perdana di bawah nombor tertentu . Algoritma berfungsi dengan menandakan gandaan bagi setiap nombor perdana secara berulang, bermula dengan 2.

Berikut ialah pelaksanaan Python bagi Ayak Eratosthenes:

def sieve_of_eratosthenes(n):
    """Return a list of all prime numbers below n."""

    # Create a list of all numbers from 2 to n.
    numbers = list(range(2, n + 1))

    # Iterate over the numbers in the list.
    for i in range(2, int(n ** 0.5) + 1):

        # If the number is prime, mark off all its multiples.
        if numbers[i] != -1:
            for j in range(i * i, n + 1, i):
                numbers[j] = -1

    # Return the list of prime numbers.
    return [i for i in numbers if i != -1]

Algoritma ini agak mudah untuk dilaksanakan, dan ia agak cekap. Sebagai contoh, ia boleh menemui semua nombor perdana di bawah 1 juta dalam kira-kira 0.1 saat pada komputer moden.

Kerumitan Masa

Kerumitan masa Ayakan Eratosthenes ialah O(n log log n) . Ini bermakna algoritma mengambil masa O(n) untuk mencipta senarai semua nombor daripada 2 hingga n, dan masa O(log log n) diperlukan untuk menandakan semua gandaan setiap nombor perdana.

Bolehkah ia dibuat dengan lebih pantas?

Terdapat beberapa cara untuk menjadikan Sieve of Eratosthenes sekata lebih pantas:

• Gunakan struktur data yang lebih cekap. Senarai semua nombor dari 2 hingga n boleh disimpan dalam struktur data yang lebih cekap, seperti vektor bit. Ini boleh mengurangkan keperluan ruang algoritma dan meningkatkan prestasinya.
• Gunakan algoritma penandaan yang lebih cekap. Algoritma untuk menandakan semua gandaan setiap nombor perdana boleh dibuat lebih cekap dengan menggunakan roda ayak. Ini boleh mengurangkan kerumitan masa algoritma kepada O(n).
• Selarikan algoritma. Algoritma boleh diselaraskan untuk memanfaatkan berbilang teras pada komputer moden. Ini boleh meningkatkan lagi prestasi algoritma.

Berikut ialah pelaksanaan Python bagi versi Sieve of Eratosthenes yang lebih pantas:

import numpy as np

def sieve_of_eratosthenes_fast(n):
    """Return a list of all prime numbers below n."""

    # Create a bit vector to store the prime numbers.
    primes = np.ones(n // 2 + 1, dtype=np.bool)

    # Mark off all the multiples of 2.
    primes[3::2] = False

    # Iterate over the odd numbers from 3 to n.
    for i in range(3, int(n ** 0.5) + 1, 2):

        # If the number is prime, mark off all its multiples.
        if primes[i // 2]:
            primes[i * i // 2::i] = False

    # Return the list of prime numbers.
    return [2] + [2 * i + 1 for i in range(1, n // 2 + 1) if primes[i]]

Algoritma ini lebih pantas daripada versi asal daripada Sieve of Eratosthenes, dan ia boleh menemui semua bilangan prima di bawah 1 juta dalam kira-kira 0.01 saat pada komputer moden.

Atas ialah kandungan terperinci Bagaimanakah Penapisan Algoritma Eratosthenes Boleh Dioptimumkan untuk Penjanaan Nombor Perdana yang Lebih Cepat?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!