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

Hier ist eine numpy-Version des Sieb des Eratosthenes, die eine gute Komplexität (niedriger als das Sortieren eines Arrays der Länge n) und Vektorisierung hat. Im Vergleich zu den Zeiten von @unutbu ist dies genauso schnell wie die Pakete mit 46 Mikrosekunden, um alle Primzahlen unter einer Million zu finden.

import numpy as np 
def generate_primes(n):
    is_prime = np.ones(n+1,dtype=bool)
    is_prime[0:2] = False
    for i in range(int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i**2::i]=False
    return np.where(is_prime)[0]

Zeitmessungen:

import time    
for i in range(2,10):
    timer =time.time()
    generate_primes(10**i)
    print('n = 10^',i,' Zeit =', round(time.time()-timer,6))

>> n = 10^ 2  Zeit = 5.6e-05
>> n = 10^ 3  Zeit = 6.4e-05
>> n = 10^ 4  Zeit = 0.000114
>> n = 10^ 5  Zeit = 0.000593
>> n = 10^ 6  Zeit = 0.00467
>> n = 10^ 7  Zeit = 0.177758
>> n = 10^ 8  Zeit = 1.701312
>> n = 10^ 9  Zeit = 19.322478

Answer 2

Ausgehend von dieser Antwort von 2021 habe ich festgestellt, dass der bitarray-Ansatz für Primzahlen unter 1 Milliarde nicht vorteilhaft ist.

Aber ich konnte das primesfrom2to fast um das Doppelte beschleunigen mit einigen Tricks:

• Verwenden Sie die numexpr-Bibliothek, um numpy-Ausdrücke in enge Schleifen mit weniger Allokationen umzuwandeln
• Ersetzen Sie np.ones durch eine schnellere Alternative
• Manipulieren Sie die ersten 9 Elemente eines Siebes so, dass später keine Änderung der Array-Form erforderlich ist

Insgesamt ging die Zeit für Primzahlen unter 1 Milliarde auf meinem Rechner von 25s auf 14,5s

import numexpr as ne
import numpy as np

def primesfrom2to_numexpr(n):
    # https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Eingabe n>=24, gibt ein Array von Primzahlen zurück, 2 <= p < n + ein paar mehr"""
    sieve = np.zeros((n // 3 + (n % 6 == 2))//4+1, dtype=np.int32)
    ne.evaluate('sieve + 0x01010101', out=sieve)
    sieve = sieve.view('int8')
    #sieve = np.ones(n // 3 + (n % 6 == 2), dtype=np.bool_)
    sieve[0] = 0
    for i in np.arange(int(n ** 0.5) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[((k * k) // 3)::2 * k] = 0
            sieve[(k * k + 4 * k - 2 * k * (i & 1)) // 3::2 * k] = 0
    sieve[[0,8]] = 1
    result = np.flatnonzero(sieve)
    ne.evaluate('result * 3 + 1 + result%2', out=result)
    result[:9] = [2,3,5,7,11,13,17,19,23]
    return result

Answer 3

Ich bin vielleicht spät dran, aber ich muss meinen eigenen Code dafür hinzufügen. Es verwendet ungefähr n/2 Platz, weil wir keine geraden Zahlen speichern müssen, und ich nutze auch das Bitarray-Python-Modul, was den Speicherverbrauch drastisch reduziert und das Berechnen aller Primzahlen bis 1.000.000.000 ermöglicht

from bitarray import bitarray
def primes_to(n):
    size = n//2
    sieve = bitarray(size)
    sieve.setall(1)
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            sieve[(i+i*val)::val] = 0
    return [2] + [2*i+1 for i, v in enumerate(sieve) if v and i > 0]

python -m timeit -n10 -s "import euler" "euler.primes_to(1000000000)"
10 loops, best of 3: 46.5 sec per loop

Dies wurde auf einem 64-Bit 2,4-GHZ-MAC OSX 10.8.3 ausgeführt

Answer 4

Entschuldigung für die Störung, aber erat2() hat einen ernsthaften Fehler im Algorithmus.

Beim Suchen nach der nächsten zusammengesetzten Zahl müssen wir nur ungerade Zahlen testen. q,p sind beide ungerade; dann ist q+p gerade und muss nicht getestet werden, aber q+2*p ist immer ungerade. Dies eliminiert den "bei gerade" Test in der Bedingung der while-Schleife und spart etwa 30% der Laufzeit.

Während wir dabei sind: Anstelle der eleganten Methode 'D.pop(q,None)' zur Bereitstellung und Löschung verwenden Sie 'if q in D: p=D[q], del D[q]', die doppelt so schnell ist! Zumindest auf meinem Rechner (P3-1Ghz). Deshalb schlage ich die Implementierung dieses cleveren Algorithmus vor:

def erat3( ):
    from itertools import islice, count

    # q ist die laufende ganze Zahl, die auf Primzahl geprüft wird.
    # gib 2 zurück und danach keine andere gerade Zahl
    yield 2
    D = {}
    # Es ist nicht nötig, D[4] zu markieren, da wir nur ungerade Zahlen testen werden
    for q in islice(count(3),0,None,2):
        if q in D:                  #  ist zusammengesetzt
            p = D[q]
            del D[q]
            # q ist zusammengesetzt. p=D[q] ist die erste Primzahl, die
            # ihn teilt. Da wir q erreicht haben, brauchen wir ihn nicht mehr
            # in der Abbildung, aber wir werden das nächste
            # Vielfache seiner Zeugen markieren, um uns auf größere
            # Zahlen vorzubereiten.
            x = q + p+p        # nächste ungerade(!) Vielfache
            while x in D:      # überspringe Zusammengesetzte
                x += p+p
            D[x] = p
        else:                  # ist Primzahl
            # q ist eine neue Primzahl.
            # Gib sie zurück und markiere ihr erstes Vielfaches, das nicht
            # bereits in früheren Iterationen markiert wurde.
            D[q*q] = q
            yield q

Answer 5

Meine Vermutung ist, dass der schnellste Weg ist, die Primzahlen direkt in deinem Code fest zu kodieren.

Warum also nicht einfach ein langsames Skript schreiben, das eine weitere Quelldatei erstellt, in der alle Zahlen fest verdrahtet sind, und diese Quelldatei dann importieren, wenn du dein tatsächliches Programm ausführst.

Natürlich funktioniert dies nur, wenn du die Obergrenze von N zur Kompilierzeit kennst, was jedoch für (fast) alle Project Euler Probleme der Fall ist.

PS: Ich könnte aber falsch liegen, wenn das Parsen der Quelldatei mit fest verdrahteten Primzahlen langsamer ist als das Berechnen von ihnen von Anfang an, aber soweit ich weiß, läuft Python aus kompilierten .pyc Dateien, sodass das Lesen eines binären Arrays mit allen Primzahlen bis N in diesem Fall verdammt schnell sein sollte.