Was ist der schnellste Algorithmus, um alle Primzahlen unterhalb einer bestimmten ganzen Zahl N zu generieren?

Schnellste Methode zum Auflisten aller Primzahlen unterhalb von N: Eine Erkundung

Problem:

Bestimmen Sie die schnellste Methode zum Auflisten aller Primzahlen, die kleiner als eine bestimmte ganze Zahl sind N.

Frage:

Kann der angegebene Algorithmus für eine schnellere Ausführung optimiert werden?

Antwort:

Der bereitgestellte Algorithmus kann hinsichtlich der Geschwindigkeit erheblich verbessert werden. Ein Vergleich verschiedener Implementierungen zeigt, dass rwh_primes1 mit Psyco am effizientesten für die Generierung von Primzahlen unter 1.000.000 ist.

Zusätzliche Erkenntnisse:

• Ohne Psyco entsteht rwh_primes2 als der Schnellste Methode.
• Die Verwendung von NumPy bietet weitere Leistungsverbesserungen, wobei sich primesfrom2to als die schnellste unter allen getesteten Methoden erweist.

Implementierungsdetails:

• ambi_sieve_plain: Ein einfaches Sieb-basiertes Ansatz.
• rwh_primes, rwh_primes1 und rwh_primes2: Variationen der Algorithmen von Robert William Hanks.
• sieve_wheel_30: Ein spezieller Algorithmus, der für 30-basierte Berechnungen optimiert ist.
• sieveOfEratosthenes: Der klassische Siebmethode mit Bitset Optimierungen.
• sieveOfAtkin: Ein modernes Sieb, das Modulo-Arithmetik nutzt.
• sundaram3: Sundarams Algorithmus mit Optimierungen für Mengen kleinerer Zahlen.
• ambi_sieve: Ein siebbasierter Ansatz mit NumPy Optimierungen.
• Primzahlen von 3 bis und Primzahlen von 2 bis: NumPy-basierte Algorithmen zur effizienten Generierung von Primzahlen.

Timings:

147.0

Methode

Zeit (ms) mit Psyco

Zeit (ms) ohne Psyco

rwh_primes1

43,0

93,7

sieveOfAtkin

46,4

314,0

rwh_primes

57 .4

94,6

sieve_wheel_30

63,0

97,4

rwh_primes2

67,8

68,1

sieveOfEratosthenes

178.0

ambi_sieve_plain

152.0

286.0

sundaram3

194.0

416.0

primesfrom2to

Method	Time (ms) with Psyco	Time (ms) without Psyco
rwh_primes1	43.0	93.7
sieveOfAtkin	46.4	314.0
rwh_primes	57.4	94.6
sieve_wheel_30	63.0	97.4
rwh_primes2	67.8	68.1
sieveOfEratosthenes	147.0	178.0
ambi_sieve_plain	152.0	286.0
sundaram3	194.0	416.0
primesfrom2to	15.9	N/A
primesfrom3to	18.4	N/A
ambi_sieve	29.3	N/A

15,9

N/A

Primzahlen von 3 bis

18,4

N/A

ambi_sieve

29,3

N/A

Das obige ist der detaillierte Inhalt vonWas ist der schnellste Algorithmus, um alle Primzahlen unterhalb einer bestimmten ganzen Zahl N zu generieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!