wake-up-neo.net

Sieb von Eratosthenes - Suche nach Primaten Python

Nur um das zu klären, ist dies kein Hausaufgabenproblem :)

Ich wollte Primzahlen für eine mathematische Anwendung finden, die ich baue und auf Sieve of Eratosthenes Ansatz stieß. 

Ich habe eine Implementierung davon in Python geschrieben. Aber es ist furchtbar langsam. Zum Beispiel, wenn ich alle Primzahlen unter 2 Millionen finden möchte. Es dauert> 20 Minuten. (Ich habe es an diesem Punkt gestoppt). Wie kann ich das beschleunigen?

def primes_sieve(limit):
    limitn = limit+1
    primes = range(2, limitn)

    for i in primes:
        factors = range(i, limitn, i)
        for f in factors[1:]:
            if f in primes:
                primes.remove(f)
    return primes

print primes_sieve(2000)

UPDATE: Am Ende erstellte ich ein Profil für diesen Code und stellte fest, dass viel Zeit darauf verwendet wurde, ein Element aus der Liste zu entfernen. Ganz verständlich, wenn man bedenkt, dass man die gesamte Liste durchgehen muss (Worst-Case), um das Element zu finden und es dann zu entfernen und die Liste neu anzupassen (möglicherweise wird etwas kopiert?) Jedenfalls habe ich die Liste für das Wörterbuch herausgeschmissen. Meine neue Implementierung - 

def primes_sieve1(limit):
    limitn = limit+1
    primes = dict()
    for i in range(2, limitn): primes[i] = True

    for i in primes:
        factors = range(i,limitn, i)
        for f in factors[1:]:
            primes[f] = False
    return [i for i in primes if primes[i]==True]

print primes_sieve1(2000000)
60

Sie implementieren den richtigen Algorithmus nicht ganz:

In Ihrem ersten Beispiel führt primes_sieve keine Liste von primitiven Flags, die (wie im Algorithmus) als Strike/Unset gesetzt werden sollen. Stattdessen wird die Liste der Ganzzahlen fortlaufend geändert Artikel um eins herunter.

Im zweiten Beispiel verwaltet primes_sieve1 ein dictionary von Primality-Flags, was einen Schritt in die richtige Richtung darstellt, aber es durchläuft das Wörterbuch in undefinierter Reihenfolge und schlägt redundante Faktoren (statt nur Primfaktoren) hervor wie im Algorithmus). Sie können dies beheben, indem Sie die Schlüssel sortieren und Nicht-Primzahlen überspringen (was die Reihenfolge bereits um eine Größenordnung beschleunigt). Es ist jedoch viel effizienter, eine Liste direkt zu verwenden.

Der korrekte Algorithmus (mit einer Liste anstelle eines Wörterbuchs) sieht ungefähr so ​​aus:

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in xrange(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

(Beachten Sie, dass dies auch die algorithmische Optimierung des Startens der Nicht-Prim-Markierung am Quadrat der Primzahl (i*i) anstelle ihres Doppelpunkts beinhaltet.)

97
Pi Delport
def eratosthenes(n):
    multiples = []
    for i in range(2, n+1):
        if i not in multiples:
            print (i)
            for j in range(i*i, n+1, i):
                multiples.append(j)

eratosthenes(100)
11
Saurabh Rana

Beim Entfernen vom Anfang eines Arrays (Liste) müssen alle Elemente nach unten verschoben werden. Das bedeutet, dass das Entfernen aller Elemente aus einer Liste auf diese Weise von vorne her eine O (n ^ 2) -Operation ist.

Mit Sets können Sie dies wesentlich effizienter durchführen:

def primes_sieve(limit):
    limitn = limit+1
    not_prime = set()
    primes = []

    for i in range(2, limitn):
        if i in not_prime:
            continue

        for f in range(i*2, limitn, i):
            not_prime.add(f)

        primes.append(i)

    return primes

print primes_sieve(1000000)

... oder alternativ vermeiden Sie eine Neuordnung der Liste:

def primes_sieve(limit):
    limitn = limit+1
    not_prime = [False] * limitn
    primes = []

    for i in range(2, limitn):
        if not_prime[i]:
            continue
        for f in xrange(i*2, limitn, i):
            not_prime[f] = True

        primes.append(i)

    return primes
6
Glenn Maynard

Durch die Kombination von Beiträgen vieler Enthusiasten (einschließlich Glenn Maynard und MrHIDEn aus den obigen Kommentaren) habe ich in Python 2 den folgenden Code gefunden:

def simpleSieve(sieveSize):
    #creating Sieve.
    sieve = [True] * (sieveSize+1)
    # 0 and 1 are not considered prime.
    sieve[0] = False
    sieve[1] = False
    for i in xrange(2,int(math.sqrt(sieveSize))+1):
        if sieve[i] == False:
            continue
        for pointer in xrange(i**2, sieveSize+1, i):
            sieve[pointer] = False
    # Sieve is left with prime numbers == True
    primes = []
    for i in xrange(sieveSize+1):
        if sieve[i] == True:
            primes.append(i)
    return primes

sieveSize = input()
primes = simpleSieve(sieveSize)

Zeitaufwand für die Berechnung meines Computers für verschiedene Eingaben bei einer Leistung von 10 ist:

  • 3: 0,3 ms
  • 4: 2,4 ms
  • 5: 23 ms
  • 6: 0,26 s
  • 7: 3,1 s
  • 8: 33 s
1
Ajay

Viel schneller:

import time
def get_primes(n):
  m = n+1
  #numbers = [True for i in range(m)]
  numbers = [True] * m #EDIT: faster
  for i in range(2, int(n**0.5 + 1)):
    if numbers[i]:
      for j in range(i*i, m, i):
        numbers[j] = False
  primes = []
  for i in range(2, m):
    if numbers[i]:
      primes.append(i)
  return primes

start = time.time()
primes = get_primes(10000)
print(time.time() - start)
print(get_primes(100))
1
MrHIDEn

Mir ist klar, dass dies nicht wirklich die Antwort auf die Frage ist, wie man Primzahlen schnell generieren kann, aber vielleicht werden einige diese Alternative interessant finden: Da Python eine faule Bewertung über Generatoren bietet, kann das Sieb von eratosthenes genau so implementiert werden:

def intsfrom(n):
    while True:
        yield n
        n += 1

def sieve(ilist):
    p = next(ilist)
    yield p
    for q in sieve(n for n in ilist if n%p != 0):
        yield q


try:
    for p in sieve(intsfrom(2)):
        print p,

    print ''
except RuntimeError as e:
    print e

Der try-Block ist vorhanden, da der Algorithmus so lange ausgeführt wird, bis er den Stack durchbrennt und ohne den Try-Block der Backtrace angezeigt wird. Dabei wird die tatsächliche Ausgabe, die Sie sehen möchten, aus dem Bildschirm geschoben.

1
Paul Gardiner

Ich dachte mir, es muss möglich sein, die leere Liste einfach als Abschlussbedingung für die Schleife zu verwenden, und kam dazu:

limit = 100
ints = list(range(2, limit))   # Will end up empty

while len(ints) > 0:
    prime = ints[0]
    print prime
    ints.remove(prime)
    i = 2
    multiple = prime * i
    while multiple <= limit:
        if multiple in ints:
            ints.remove(multiple)
        i += 1
        multiple = prime * i
0
Tom Russell

Ich ziehe NumPy wegen der Geschwindigkeit vor.

import numpy as np

# Find all prime numbers using Sieve of Eratosthenes
def get_primes1(n):
    m = int(np.sqrt(n))
    is_prime = np.ones(n, dtype=bool)
    is_prime[:2] = False  # 0 and 1 are not primes

    for i in range(2, m):
        if is_prime[i] == False:
            continue
        is_prime[i*i::i] = False

    return np.nonzero(is_prime)[0]

# Find all prime numbers using brute-force.
def isprime(n):
    ''' Check if integer n is a prime '''
    n = abs(int(n))  # n is a positive integer
    if n < 2:  # 0 and 1 are not primes
        return False
    if n == 2:  # 2 is the only even prime number
        return True
    if not n & 1:  # all other even numbers are not primes
        return False
    # Range starts with 3 and only needs to go up the square root
    # of n for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

# To apply a function to a numpy array, one have to vectorize the function
def get_primes2(n):
    vectorized_isprime = np.vectorize(isprime)
    a = np.arange(n)
    return a[vectorized_isprime(a)]

Überprüfen Sie die Ausgabe:

n = 100
print(get_primes1(n))
print(get_primes2(n))    
    [ 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]
    [ 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]

Vergleichen Sie die Geschwindigkeit von Sieve of Eratosthenes und Brute-Force auf Jupyter Notebook. Sieb von Eratosthenes in 539-mal schneller als Brute-Force für Millionen Elemente. 

%timeit get_primes1(1000000)
%timeit get_primes2(1000000)
4.79 ms ± 90.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
2.58 s ± 31.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
0
foo bar

ich denke, dies ist der kürzeste Code zum Finden von Primzahlen mit der Eratosthenes-Methode

def prime(r):
    n = range(2,r)
    while len(n)>0:
        yield n[0]
        n = [x for x in n if x not in range(n[0],r,n[0])]


print(list(prime(r)))
0
Pythoscorpion

Meine schnellste Implementierung:

isprime = [True]*N
isprime[0] = isprime[1] = False
for i in range(4, N, 2):
    isprime[i] = False
for i in range(3, N, 2):
    if isprime[i]:
        for j in range(i*i, N, 2*i):
            isprime[j] = False
0
Madiyar

Hier ist eine Version, die etwas speichereffizienter ist (und: ein richtiges Sieb, keine Probedivisionen). Anstatt ein Array mit allen Zahlen zu speichern und diejenigen zu streichen, die keine Primzahlen sind, behält dies eine Reihe von Zählern bei - einer für jede Primzahl, die entdeckt wird - und springt sie vor der möglichen Primzahl an. Auf diese Weise wird der Speicher proportional zur Anzahl der Primzahlen verwendet, nicht bis zur höchsten Primzahl.

import itertools

def primes():

    class counter:
        def __init__ (this,  n): this.n, this.current,  this.isVirgin = n, n*n,  True
            # isVirgin means it's never been incremented
        def advancePast (this,  n): # return true if the counter advanced
            if this.current > n:
                if this.isVirgin: raise StopIteration # if this is virgin, then so will be all the subsequent counters.  Don't need to iterate further.
                return False
            this.current += this.n # pre: this.current == n; post: this.current > n.
            this.isVirgin = False # when it's gone, it's gone
            return True

    yield 1
    multiples = []
    for n in itertools.count(2):
        isPrime = True
        for p in (m.advancePast(n) for m in multiples):
            if p: isPrime = False
        if isPrime:
            yield n
            multiples.append (counter (n))

Sie werden feststellen, dass primes() ein Generator ist, also können Sie die Ergebnisse in einer Liste halten oder direkt verwenden. Hier sind die ersten n Primes:

import itertools

for k in itertools.islice (primes(),  n):
    print (k)

Der Vollständigkeit halber ist hier ein Timer zum Messen der Leistung:

import time

def timer ():
    t,  k = time.process_time(),  10
    for p in primes():
        if p>k:
            print (time.process_time()-t,  " to ",  p,  "\n")
            k *= 10
            if k>100000: return

Nur für den Fall, dass Sie sich fragen, schrieb ich primes() als einfachen Iterator (mit __iter__ und __next__), und es lief fast mit derselben Geschwindigkeit. Überrascht mich auch!

0
Jules May

Meine Implementierung:

import math
n = 100
marked = {}
for i in range(2, int(math.sqrt(n))):
    if not marked.get(i):
        for x in range(i * i, n, i):
            marked[x] = True

for i in range(2, n):
    if not marked.get(i):
        print i
0
SilentDirge

Ein einfacher Speed-Hack: Wenn Sie die Variable "Primes" definieren, setzen Sie den Schritt auf 2, um alle geraden Zahlen automatisch zu überspringen und den Startpunkt auf 1 zu setzen.

Dann können Sie weiter optimieren, indem Sie anstelle von i in Primzahlen [i] in Primzahlen [: round (len (primes) ** 0,5)] verwenden. Das wird die Leistung drastisch steigern. Darüber hinaus können Sie mit 5 endende Zahlen eliminieren, um die Geschwindigkeit weiter zu erhöhen.

0
user3917838
import math
def sieve(n):
    primes = [True]*n
    primes[0] = False
    primes[1] = False
    for i in range(2,int(math.sqrt(n))+1):
            j = i*i
            while j < n:
                    primes[j] = False
                    j = j+i
    return [x for x in range(n) if primes[x] == True]
0
Nestorghh