Schnellster Weg, um alle Primzahlen unter N aufzulisten

Question

Dies ist der beste Algorithmus, den ich entwickeln konnte.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
1.1499958793645562

Kann er noch schneller gemacht werden?

Dieser Code hat ein Problem: Da numbers eine ungeordnete Menge ist, gibt es keine Garantie dafür, dass numbers.pop() die niedrigste Zahl aus der Menge entfernt. Trotzdem funktioniert es (zumindest für mich) für einige Eingabelnummern:

>>> sum(get_primes(2000000))
142913828922L
#Das ist die korrekte Summe aller Zahlen unter 2 Millionen
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True

Answer 1

Ich bin langsam in meiner Antwort auf diese Frage, aber es schien mir eine spaßige Übung zu sein. Ich verwende numpy, was vielleicht betrügen ist, und ich bezweifle, dass diese Methode die schnellste ist, aber sie sollte klar sein. Es siebt ein boolesches Array, das sich nur auf seine Indizes bezieht, und ruft Primzahlen aus den Indizes aller True-Werte ab. Kein Modulo erforderlich.

import numpy as np
def ajs_primes3a(upto):
    mat = np.ones((upto), dtype=bool)
    mat[0] = False
    mat[1] = False
    mat[4::2] = False
    for idx in range(3, int(upto ** 0.5)+1, 2):
        mat[idx*2::idx] = False
    return np.where(mat == True)[0]

Answer 2

Im Laufe der Zeit habe ich mehrere Primzahl-Siebe gesammelt. Das schnellste auf meinem Computer ist dieses:

from time import time
# 175 ms für alle Primzahlen bis zum Wert 10**6
def primes_sieve(limit):
    a = [True] * limit
    a[0] = a[1] = False
    #a[2] = True
    for n in xrange(4, limit, 2):
        a[n] = False
    root_limit = int(limit**.5)+1
    for i in xrange(3,root_limit):
        if a[i]:
            for n in xrange(i*i, limit, 2*i):
                a[n] = False
    return a

LIMIT = 10**6
s=time()
primes = primes_sieve(LIMIT)
print time()-s

Answer 3

Ich habe einen reinen Python 2 Primzahlengenerator hier gefunden, in einem Kommentar von Willy Good, der schneller ist als rwh2_primes.

def primes235(limit):
yield 2; yield 3; yield 5
if limit < 7: return
modPrms = [7,11,13,17,19,23,29,31]
gaps = [4,2,4,2,4,6,2,6,4,2,4,2,4,6,2,6] # 2 loops for overflow
ndxs = [0,0,0,0,1,1,2,2,2,2,3,3,4,4,4,4,5,5,5,5,5,5,6,6,7,7,7,7,7,7]
lmtbf = (limit + 23) // 30 * 8 - 1 # integral number of wheels rounded up
lmtsqrt = (int(limit ** 0.5) - 7)
lmtsqrt = lmtsqrt // 30 * 8 + ndxs[lmtsqrt % 30] # round down on the wheel
buf = [True] * (lmtbf + 1)
for i in xrange(lmtsqrt + 1):
    if buf[i]:
        ci = i & 7; p = 30 * (i >> 3) + modPrms[ci]
        s = p * p - 7; p8 = p << 3
        for j in range(8):
            c = s // 30 * 8 + ndxs[s % 30]
            buf[c::p8] = [False] * ((lmtbf - c) // p8 + 1)
            s += p * gaps[ci]; ci += 1
for i in xrange(lmtbf - 6 + (ndxs[(limit - 7) % 30])): # adjust for extras
    if buf[i]: yield (30 * (i >> 3) + modPrms[i & 7])

Meine Ergebnisse:

$ time ./prime_rwh2.py 1e8
5761455 gefundene Primzahlen < 1e8

real    0m3.201s
user    0m2.609s
sys     0m0.578s
$ time ./prime_wheel.py 1e8
5761455 gefundene Primzahlen < 1e8

real    0m2.710s
user    0m2.469s
sys     0m0.219s

...auf meinem aktuellen Mittelklasse-Laptop (i5 8265U 1,6 GHz) mit Ubuntu auf Win 10.

Das ist ein Modulo-30-Radsieb, das Vielfache von 2, 3 und 5 überspringt. Es funktioniert für mich bis etwa 2,5e9 gut, wenn mein Laptop anfängt, viel Arbeitsspeicher zu verbrauchen und stark zu tauschen.

Ich mag Modulo 30, da es nur 8 Reste gibt, die keine Vielfachen von 2, 3 oder 5 sind. Das ermöglicht die Verwendung von Verschiebungen und "&" für Multiplikation, Division und Modulo und sollte das Verpacken von Ergebnissen für ein Modulo-30-Rad in ein Byte ermöglichen. Ich habe Willys Code in ein segmentiertes Modulo-30-Radsieb umgewandelt, um das Thrashing für große N zu eliminieren, und es hier veröffentlicht.

Es gibt sogar eine schnellere Javascript-Version, die segmentiert ist und ein Modulo-210-Rad verwendet (keine Vielfachen von 2, 3, 5 oder 7) von @GordonBGood mit einer ausführlichen Erklärung, die für mich nützlich ist.

Answer 4

Dies ist eine Variation der Lösung in der Frage, die schneller sein sollte als das, was in der Frage steht. Es verwendet ein statisches Sieb des Eratosthenes ohne weitere Optimierungen.

from typing import List

def list_primes(limit: int) -> List[int]:
    primes = set(range(2, limit + 1))
    for i in range(2, limit + 1):
        if i in primes:
            primes.difference_update(set(list(range(i, limit + 1, i))[1:]))
    return sorted(primes)

>>> list_primes(100)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Answer 5

Die schnellste Methode, die ich bisher ausprobiert habe, basiert auf der Python Kochbuch erat2 Funktion:

import itertools as it
def erat2a( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

Siehe diese Antwort für eine Erklärung zur Geschwindigkeitssteigerung.