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

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 2

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 3

Ich habe einige Funktionen von unutbu getestet, ich habe sie mit hundert Millionen Zahlen berechnet

Die Gewinner sind die Funktionen, die die numpy-Bibliothek verwenden,

Hinweis: Es wäre auch interessant, einen Speicherverbrauchstest durchzuführen :)

Beispielcode

Vollständiger Code in meinem GitHub-Repository

#!/usr/bin/env python

import lib
import timeit
import sys
import math
import datetime

import prettyplotlib as ppl
import numpy as np

import matplotlib.pyplot as plt
from prettyplotlib import brewer2mpl

primenumbers_gen = [
    'sieveOfEratosthenes',
    'ambi_sieve',
    'ambi_sieve_plain',
    'sundaram3',
    'sieve_wheel_30',
    'primesfrom3to',
    'primesfrom2to',
    'rwh_primes',
    'rwh_primes1',
    'rwh_primes2',
]

def human_format(num):
    # https://stackoverflow.com/questions/579310/formatting-long-numbers-as-strings-in-python?answertab=active#tab-top
    magnitude = 0
    while abs(num) >= 1000:
        magnitude += 1
        num /= 1000.0
    # add more suffixes if you need them
    return '%.2f%s' % (num, ['', 'K', 'M', 'G', 'T', 'P'][magnitude])

if __name__=='__main__':

    # Vars
    n = 10000000 # Anzahl der Iterationen des Generators
    nbcol = 5 # Zur Zerlegung des Primzahlerzeugers
    nb_benchloop = 3 # Falsch positive Werte während des Tests eliminieren (Test durchschnittliche Zeit)
    datetimeformat = '%Y-%m-%d %H:%M:%S.%f'
    config = 'from __main__ import n; import lib'
    primenumbers_gen = {
        'sieveOfEratosthenes': {'color': 'b'},
        'ambi_sieve': {'color': 'b'},
        'ambi_sieve_plain': {'color': 'b'},
         'sundaram3': {'color': 'b'},
        'sieve_wheel_30': {'color': 'b'},
# # #        'primesfrom2to': {'color': 'b'},
        'primesfrom3to': {'color': 'b'},
        # 'rwh_primes': {'color': 'b'},
        # 'rwh_primes1': {'color': 'b'},
        'rwh_primes2': {'color': 'b'},
    }

    # n von der Befehlszeile erhalten
    if len(sys.argv)>1:
        n = int(sys.argv[1])

    step = int(math.ceil(n / float(nbcol)))
    nbs = np.array([i * step for i in range(1, int(nbcol) + 1)])
    set2 = brewer2mpl.get_map('Paired', 'qualitative', 12).mpl_colors

    print datetime.datetime.now().strftime(datetimeformat)
    print("Berechne Primzahlen bis %(n)s" % locals())
    print("")

    results = dict()
    for pgen in primenumbers_gen:
        results[pgen] = dict()
        benchtimes = list()
        for n in nbs:
            t = timeit.Timer("lib.%(pgen)s(n)" % locals(), setup=config)
            execute_times = t.repeat(repeat=nb_benchloop, number=1)
            benchtime = np.mean(execute_times)
            benchtimes.append(benchtime)
        results[pgen] = {'benchtimes': np.array(benchtimes)}

fig, ax = plt.subplots(1)
plt.ylabel('Rechenzeit (in Sekunden)')
plt.xlabel('Berechnete Zahlen')
i = 0
for pgen in primenumbers_gen:

    bench = results[pgen]['benchtimes']
    avgs = np.divide(bench, nbs)
    avg = np.average(bench, weights=nbs)

    # Lineare Regression berechnen
    A = np.vstack([nbs, np.ones(len(nbs))]).T
    a, b = np.linalg.lstsq(A, nbs*avgs)[0]

    # Plot
    i += 1
    #label="%(pgen)s" % locals()
    #ppl.plot(nbs, nbs*avgs, label=label, lw=1, linestyle='--', color=set2[i % 12])
    label="%(pgen)s avg" % locals()
    ppl.plot(nbs, a * nbs + b, label=label, lw=2, color=set2[i % 12])
print datetime.datetime.now().strftime(datetimeformat)

ppl.legend(ax, loc='oben links', ncol=4)

# Ändern Sie das Beschriftung der x-Achse
ax.get_xaxis().get_major_formatter().set_scientific(False)
fig.canvas.draw()
labels = [human_format(int(item.get_text())) for item in ax.get_xticklabels()]

ax.set_xticklabels(labels)
ax = plt.gca()

plt.show()

Answer 4

Für Python 3

def rwh_primes2(n):
    correction = (n%6>1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n//3)
    sieve[0] = False
    for i in range(int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      ((k*k)//3)      ::2*k]=[False]*((n//6-(k*k)//6-1)//k+1)
        sieve[(k*k+4*k-2*k*(i&1))//3::2*k]=[False]*((n//6-(k*k+4*k-2*k*(i&1))//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

Answer 5

Der einfachste Weg, den ich gefunden habe, um dies zu tun, lautet:

primes = []
for n in range(low, high + 1):
    if all(n % i for i in primes):
        primes.append(n)