Im nachfolgenden Teil werden wir versuchen, einen Primzahlfilter zu schreiben, der uns die Primzahlen aus einem gegebenen Intervall zurückgibt.
Eine Primzahl ist eine Zahl die nur durch sich selbst und durch eins Teilbar ist. 1 (Eins) ist keine Primzahl. 2 (Zwei) ist die erste Primzahl und die einzig gerade. Mit diesem Wissen koennen wir nun anfangen
Um zu überprüfen, ob eine gegebende Zahl durch eine andere Zahl teilbar ist, können wir den Modulo-Operator (%) nutzen. Dieser gibt den Rest bei einer ganzzahligen Teilung wieder. Ist a also durch b teilbar, dann ist a % b 0. Dies können wir wie folgt schreiben:
12 % 4 == 0
True
Wir schreiben eine Funktion, die:
def is_prime(a):
if a == 1:
return False
for i in range(2, a):
if a % i == 0:
return False
return True
is_prime(2)
True
Diese Funktion funktioniert und entscheided wahrheitsgemäß, ob es sich bei dem Argument um eine Primzahl handelt oder nicht. Nun werden wir eine Liste an Primzahlen ausgeben. Hier zwei Ansaetze:
def primelist(upper_boundry):
primes = []
for i in range(2, upper_boundry):
if is_prime(i):
primes.append(i)
return primes
primelist(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
def primelist_filter(upper_boundry):
return list(filter(is_prime, range(1, upper_boundry)))
primelist_filter(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Nun haben wir einen "Primzahlgenerator", der uns eine List von Primzahlen ausgibt. Allerdings ist dieser Ansatz ziemlich ineffizient. Wie koennte man den Generator nun verbessern?
Jede natuerliche Zahl, die keine Primzahl ist, laesst sich als produkt aus Primzahlen darstellen. Die Zahl 10 laesst sich in die Primzahlfaktoren 5 und 2 zerlegen.
Primzahlfaktoren anderer Zahlen:
10 -> [2, 5] 12 -> [2, 2, 3] 14 -> [2, 7] 27 -> [3, 9]
Also: Wenn eine Zahl keine Primzahl ist, laesst sie sich also als Produkt von Primzahlen darstellen. Somit muessen wir bei der Probe von Primzahlen nur pruefen, ob unser Kandidat durch irgendeine Primzahl teilbar ist.
def faster_primecheck(candidate, found_primes):
for i in found_primes:
if candidate % i == 0:
return found_primes
found_primes.append(candidate)
return found_primes
faster_primecheck(3,[2])
[2, 3]
Die Funktion gibt uns eine Liste zurueck, die eventuell ein neues Element enthaelt. Wenn der Kandidat hinzugefuegt wurde dann handelt es sich entweder um eine Primzahl, oder found_primes
ist zu kurz. Nun schreiben wir einen Generator basierend auf diesen Erkenntnissen:
def faster_primelist(upper_limit):
primes = []
for i in range(2, upper_limit):
primes = faster_primecheck(i, primes)
return primes
faster_primelist(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]