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

Es ist lehrreich, Ihren eigenen Code zur Primzahlfindung zu schreiben, aber es ist auch nützlich, eine schnelle und zuverlässige Bibliothek zur Hand zu haben. Ich habe einen Wrapper um die C++-Bibliothek primesieve geschrieben, ihn primesieve-python genannt.

Probieren Sie es aus pip install primesieve

import primesieve
primes = primesieve.generate_primes(10**8)

Ich wäre neugierig zu sehen, wie sich die Geschwindigkeit im Vergleich dazu verhält.

Answer 2

Eine etwas andere Implementierung eines Halbsiebs mit Numpy:

http://rebrained.com/?p=458

import math
import numpy
def prime6(upto):
    primes=numpy.arange(3,upto+1,2)
    isprime=numpy.ones((upto-1)/2,dtype=bool)
    for factor in primes\[:int(math.sqrt(upto))\]:
        if isprime\[(factor-2)/2\]: isprime\[(factor\*3-2)/2:(upto-1)/2:factor\]=0
    return numpy.insert(primes\[isprime\],0,2)

Kann jemand dies mit den anderen Zeiten vergleichen? Auf meinem Rechner scheint es ziemlich vergleichbar mit dem anderen Numpy-Halbsieb zu sein.

Answer 3

Schnellstes Primzahlsieb in Pure Python:

from itertools import compress

def half_sieve(n):
    """
    Gibt eine Liste von Primzahlen zurück, die kleiner als `n` sind.
    """
    if n <= 2:
        return []
    sieve = bytearray([True]) * (n // 2)
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i // 2]:
            sieve[i * i // 2::i] = bytearray((n - i * i - 1) // (2 * i) + 1)
    primes = list(compress(range(1, n, 2), sieve))
    primes[0] = 2
    return primes

I optimierte das Sieb des Eratosthenes für Geschwindigkeit und Speicherplatz.

Leistungstest

from time import clock
import platform

def benchmark(iterations, limit):
    start = clock()
    for x in range(iterations):
        half_sieve(limit)
    end = clock() - start
    print(f'{end/iterations:.4f} Sekunden für Primzahlen < {limit}')

if __name__ == '__main__':
    print(platform.python_version())
    print(platform.platform())
    print(platform.processor())
    it = 10
    for pw in range(4, 9):
        benchmark(it, 10**pw)

Ergebnis

>>> 3.6.7
>>> Windows-10-10.0.17763-SP0
>>> Intel64 Family 6 Model 78 Stepping 3, GenuineIntel
>>> 0.0003 Sekunden für Primzahlen < 10000
>>> 0.0021 Sekunden für Primzahlen < 100000
>>> 0.0204 Sekunden für Primzahlen < 1000000
>>> 0.2389 Sekunden für Primzahlen < 10000000
>>> 2.6702 Sekunden für Primzahlen < 100000000

Answer 4

Hier ist der Code, den ich normalerweise verwende, um Primzahlen in Python zu generieren:

$ python -mtimeit -s'import sieve' 'sieve.sieve(1000000)' 
10 Schleifen, bestes von 3: 445 msec pro Schleife
$ cat sieve.py
from math import sqrt

def sieve(size):
 prime=[True]*size
 rng=xrange
 limit=int(sqrt(size))

 for i in rng(3,limit+1,+2):
  if prime[i]:
   prime[i*i::+i]=[False]*len(prime[i*i::+i])

 return [2]+[i for i in rng(3,size,+2) if prime[i]]

if __name__=='__main__':
 print sieve(100)

Es kann nicht mit den schnelleren Lösungen konkurrieren, die hier gepostet wurden, aber zumindest ist es reines Python.

Danke für das Posten dieser Frage. Ich habe heute wirklich viel gelernt.

Answer 5

Ein deterministischer Implementierung des Miller-Rabin-Primzahltests unter der Annahme, dass N < 9.080.191 ist

import sys

def miller_rabin_pass(a, n):
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1

    a_to_power = pow(a, d, n)
    if a_to_power == 1:
        return True
    for i in range(s-1):
        if a_to_power == n - 1:
            return True
        a_to_power = (a_to_power * a_to_power) % n
    return a_to_power == n - 1

def miller_rabin(n):
    if n <= 2:
        return n == 2

    if n < 2_047:
        return miller_rabin_pass(2, n)

    return all(miller_rabin_pass(a, n) for a in (31, 73))

n = int(sys.argv[1])
primes = [2]
for p in range(3,n,2):
  if miller_rabin(p):
    primes.append(p)
print len(primes)

Laut Artikel auf Wikipedia (http://en.wikipedia.org/wiki/Miller–Rabin_primality_test) ist es ausreichend, N für a = 31 und 73 zu testen, um zu entscheiden, ob N zusammengesetzt ist oder nicht.

Und ich habe den Quellcode von der probabilistischen Implementierung des originalen Miller-Rabin-Tests angepasst, die hier zu finden ist: https://www.literateprograms.org/miller-rabin_primality_test__python_.html