Ich weiß, dass der Wettbewerb seit einigen Jahren geschlossen ist. …
Dies ist dennoch mein Vorschlag für ein reines Python-Primzahl-Sieb, basierend auf der Auslassung der Vielfachen von 2, 3 und 5 durch die Verwendung geeigneter Schritte beim Voranschreiten des Siebes. Trotzdem ist es tatsächlich langsamer für N<10^9 als die überlegenen Lösungen von @Robert William Hanks rwh_primes2 und rwh_primes1. Durch die Verwendung eines ctypes.c_ushort-Siebarrays über 1,5 * 10^8 ist es irgendwie an die Speichergrenzen anpassbar.
10^6
$ python -mtimeit -s"import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq(1000000)" 10 Schleifen, bester von 3: 46,7 msec pro Schleife
Zum Vergleich: $ python -mtimeit -s"import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1(1000000)" 10 Schleifen, bester von 3: 43,2 msec pro Schleife Zum Vergleich: $ python -m timeit -s"import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2(1000000)" 10 Schleifen, bester von 3: 34,5 msec pro Schleife
10^7
$ python -mtimeit -s"import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq(10000000)" 10 Schleifen, bester von 3: 530 msec pro Schleife
Zum Vergleich: $ python -mtimeit -s"import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1(10000000)" 10 Schleifen, bester von 3: 494 msec pro Schleife Zum Vergleich: $ python -m timeit -s"import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2(10000000)" 10 Schleifen, bester von 3: 375 msec pro Schleife
10^8
$ python -mtimeit -s"import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq(100000000)" 10 Schleifen, bester von 3: 5,55 Sek. pro Schleife
Zum Vergleich: $ python -mtimeit -s"import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1(100000000)" 10 Schleifen, bester von 3: 5,33 Sek. pro Schleife Zum Vergleich: $ python -m timeit -s"import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2(100000000)" 10 Schleifen, bester von 3: 3,95 Sek. pro Schleife
10^9
$ python -mtimeit -s"import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq(1000000000)" 10 Schleifen, bester von 3: 61,2 Sek. pro Schleife
Zum Vergleich: $ python -mtimeit -n 3 -s"import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1(1000000000)" 3 Schleifen, bester von 3: 97,8 Sek. pro Schleife
Zum Vergleich: $ python -m timeit -s"import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2(1000000000)" 10 Schleifen, bester von 3: 41,9 Sek. pro Schleife
Sie können den untenstehenden Code in dem PrimeSieveSpeedComp in Ubuntu kopieren, um diese Tests zu überprüfen.
def primeSieveSeq(MAX_Int):
if MAX_Int > 5*10**8:
import ctypes
int16Array = ctypes.c_ushort * (MAX_Int >> 1)
sieve = int16Array()
#print 'benutzt ctypes "unsigned short int Array"'
else:
sieve = (MAX_Int >> 1) * [False]
#print 'benutzt python list() von long long int'
if MAX_Int < 10**8:
sieve[4::3] = [True]*((MAX_Int - 8)/6+1)
sieve[12::5] = [True]*((MAX_Int - 24)/10+1)
r = [2, 3, 5]
n = 0
for i in xrange(int(MAX_Int**0.5)/30+1):
n += 3
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 2
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 1
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 2
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 1
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 2
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 3
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 1
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
if MAX_Int < 10**8:
return [2, 3, 5]+[(p << 1) + 1 for p in [n for n in xrange(3, MAX_Int >> 1) if not sieve[n]]]
n = n >> 1
try:
for i in xrange((MAX_Int-2*n)/30 + 1):
n += 3
if not sieve[n]:
r.append((n << 1) + 1)
n += 2
if not sieve[n]:
r.append((n << 1) + 1)
n += 1
if not sieve[n]:
r.append((n << 1) + 1)
n += 2
if not sieve[n]:
r.append((n << 1) + 1)
n += 1
if not sieve[n]:
r.append((n << 1) + 1)
n += 2
if not sieve[n]:
r.append((n << 1) + 1)
n += 3
if not sieve[n]:
r.append((n << 1) + 1)
n += 1
if not sieve[n]:
r.append((n << 1) + 1)
except:
pass
return r
0 Stimmen
Der Code-Schnipsel ist viel schneller, wenn Zahlen wie Zahlen = set(range(n, 2, -2)) deklariert werden. Aber kann sundaram3 nicht schlagen. Danke für die Frage.
4 Stimmen
Es wäre schön, wenn es Python 3-Versionen der Funktionen in den Antworten geben könnte.
0 Stimmen
Sicher gibt es eine Bibliothek, um dies zu tun, damit wir nicht selbst programmieren müssen. Xkcd versprach, dass Python so einfach ist wie
import antigravity
. Gibt es nicht so etwas wierequire 'prime'; Prime.take(10)
(Ruby)?0 Stimmen
Beachten Sie, dass Sie kein Set als Argument an
difference_update
übergeben müssen. Sie können einfachnumbers.difference_update(xrange(p*2, N+1, p))
tun. Das wird zumindest ein paar Millisekunden von Ihrer Zeit abziehen.2 Stimmen
Ich vermute, dass eine Python-Anbindung an die C++-Bibliothek primesieve um Größenordnungen schneller wäre als all diese.
4 Stimmen
@ColonelPanic Wie es sich herausstellt, habe ich github.com/jaredks/pyprimesieve für Py3 aktualisiert und zu PyPi hinzugefügt. Es ist sicherlich schneller als diese, aber nicht um Größenordnungen - eher etwa ~5x schneller als die besten numpy-Versionen.
0 Stimmen
Ich kenne den Geschwindigkeitsvergleich zu den bereits hier aufgelisteten Antworten nicht, ich würde jedoch empfehlen, sich sagemath.org anzusehen. Es handelt sich um ein Python-Krypto-Framework, das viele integrierte Funktionen hat, um die Dinge zu tun, nach denen Sie suchen.
4 Stimmen
@ColonelPanic: Ich denke, es ist angemessen, alte Antworten zu bearbeiten, um anzugeben, dass sie gealtert sind, da dies sie zu einer nützlicheren Ressource macht. Wenn die "akzeptierte" Antwort nicht mehr die beste ist, könnte man vielleicht eine Notiz in die Frage einfügen mit einem Update von 2015, um die Leute auf die aktuell beste Methode hinzuweisen.
0 Stimmen
Ich kann nicht glauben, dass kein Moderator diese Frage gelöscht hat. Sie bittet um Verbesserung in der Geschwindigkeit eines Algorithmus, der zugegebenermaßen nicht korrekt ist. Grüße, Albert
0 Stimmen
from sympy import sieve; sieve.extend(N);
0 Stimmen
Hey, das ist wirklich schneller Code. Du hast recht, der Code funktioniert für
n =10000
nicht, danumber.pop()
nicht das kleinste Element als ungeordnetes auslöst. Thread