Wie kann der Sieve of Eratosthenes-Algorithmus für eine schnellere Primzahlgenerierung optimiert werden?

Das Sieb des Eratosthenes

Das Sieb des Eratosthenes ist ein alter Algorithmus, der jedoch auch heute noch als einfache und effiziente Methode verwendet wird, um alle Primzahlen unterhalb einer bestimmten Zahl zu finden . Der Algorithmus funktioniert, indem er iterativ Vielfache jeder Primzahl markiert, beginnend mit 2.

Hier ist eine Python-Implementierung des Siebes des 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]

Dieser Algorithmus ist relativ einfach zu implementieren. und es ist ziemlich effizient. Beispielsweise kann es auf einem modernen Computer alle Primzahlen unter 1 Million in etwa 0,1 Sekunden finden.

Zeitkomplexität

Die Zeitkomplexität des Siebes des Eratosthenes beträgt O(n log log n) . Das bedeutet, dass der Algorithmus O(n) Zeit benötigt, um die Liste aller Zahlen von 2 bis n zu erstellen, und dass er O(log log n) Zeit benötigt, um alle Vielfachen jeder Primzahl zu markieren.

Kann es noch schneller gemacht werden?

Es gibt einige Möglichkeiten, das Sieb des Eratosthenes gleichmäßiger zu machen schneller:

• Verwenden Sie eine effizientere Datenstruktur. Die Liste aller Zahlen von 2 bis n kann in einer effizienteren Datenstruktur, beispielsweise einem Bitvektor, gespeichert werden. Dies kann den Platzbedarf des Algorithmus reduzieren und seine Leistung verbessern.
• Verwenden Sie einen effizienteren Markierungsalgorithmus. Der Algorithmus zum Markieren aller Vielfachen jeder Primzahl kann effizienter gestaltet werden durch Verwendung eines Siebrades. Dies kann die zeitliche Komplexität des Algorithmus auf O(n) reduzieren.
• Parallelisieren Sie den Algorithmus. Der Algorithmus kann parallelisiert werden, um die Vorteile mehrerer Kerne auf einem modernen Computer zu nutzen. Dies kann die Leistung des Algorithmus weiter verbessern.

Hier ist eine Python-Implementierung einer schnelleren Version des Siebes des Eratosthenes:

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]]

Dieser Algorithmus ist schneller als die Originalversion des Siebs des Eratosthenes und kann auf einem modernen Computer alle Primzahlen unter 1 Million in etwa 0,01 Sekunden finden.

Das obige ist der detaillierte Inhalt vonWie kann der Sieve of Eratosthenes-Algorithmus für eine schnellere Primzahlgenerierung optimiert werden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!