Voraussetzung: Sieb des Eratosthenes

Was ist der Sieve of Eratosthenes- Algorithmus?
Um es zu analysieren, nehmen wir eine Zahl n und die Aufgabe besteht darin, die Primzahlen kleiner als n zu drucken. Daher muss es nach Definition von Sieve of Eratosthenes für jede Primzahl die Vielfachen der Primzahl überprüfen und sie als zusammengesetzt markieren. Dieser Prozess setzt sich fort bis zu einem Wert p , der die höchste Primzahl kleiner als n ist .

Verstehen der n*log(log n)-Zeitkomplexität von Sieve of Eratosthenes

  1. Wenn angenommen wird, dass die Zeit, die benötigt wird, um eine Zahl als zusammengesetzt zu markieren, konstant ist, dann ist die Anzahl der Durchläufe der Schleife gleich:

  2. Wenn man n common aus der obigen Gleichung nimmt, kann die obige Gleichung umgeschrieben werden als:


  3. Es kann wie folgt mit Hilfe der harmonischen Progression der Summe der Primzahlen bewiesen werden :

    Beweis der harmonischen Progression der Summe der Primzahlen:
    Voraussetzung für das Verständnis des Beweises ist die Harmonische Reihen- und Taylorreihenentwicklung .

    • Nehmen wir die Gleichung:
    • Die Taylor-Reihenentwicklung der obigen Gleichung ist gegeben durch:
    • Wenn wir x = 1 in die obige Gleichung einsetzen, erhalten wir die Beziehung:

      Markieren wir die obige Gleichung als 1 .

    • Aus Eulers Produktformel ,

    • Wenn wir s = 1 in die obige Gleichung einsetzen, erhalten wir



    • Beim Anbringen von Log auf beiden Seiten:
      ul
    • Bei Vereinfachung der obigen Gleichung wird es:

    • In der obigen Gleichung gilt 1 > p -1 > -1
    • Daher können wir die Taylor-Reihenentwicklung für die rechte Seite der obigen Gleichung verwenden.
    • Wenn wir dies in die obige Gleichung einsetzen, erhalten wir:

      wobei p eine Primzahl ist.

    • Über die Erweiterung der inneren Summation;

    • Die obige Reihe ist konvergent. Die obige Reihe kann also angenähert werden zu:
    • Daher beim Ersetzen und Umschreiben der Gleichung; wir bekommen

      wobei p die Primzahl ist.

    • Aus der Anfangsgleichung 1 können wir schließlich schließen: wobei p die Summe der Primzahlen ist.

  4. Wenn wir dies in die Gleichung einsetzen, erhalten wir die Zeitkomplexität als:

Daher ist die Zeitkomplexität von Sieve of Eratosthenes n*log(log(n))

Referenz: Divergenz der Summe der Kehrwerte der Primzahlen

Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .