Einen hab ich noch.. einen noch.
Im folgenden habe ich das Primteiler-Verfahren mal um die üblichen Optimierungen ergänzt und (
TATA !!!) die einzige Modulo (Division) im Code eliminiert.
Mit der
prim_modulo Klasse kann für einen gegebene Divisor (Primzahl) entschieden werden ob eine Zahl aus einer steigenden Zahlenreihe Ohne Rest teilbar ist oder nicht.
Im Prinzip passiert in der prim_modulo Klasse das selbe was im Primzahlensieb geschieht, es wird geprüft ob eine Zahl gleich dem vielfachen der Primzahlen ist. Da die Primzahlenkandidaten in monoton-steigender Reihe getestet werden, kann das Vielfache einer Primzahl schrittweise mit entwickelt werden.
Ich hab gestern eine Abhandlung über dieses Verfahren gelesen und war überrascht wie einfach es zu implementieren war.
Enttäuscht war ich jedoch von der Python Performance - allein pypy schaft es diesen Code schneller als eine Modulo Variante auszuführen. Ist aber schon klar das es schwer wird mit reinen Interpreter-Code eine für das Problem schnellere Variante eines Buildin Symbols zuschreiben, hier wird eine C Implementierung sicherlich hilfreich sein.
Code: Alles auswählen
class prim_modulo(object):
def __init__(self, teiler):
self.teiler = teiler
self.multible = teiler + teiler
def mod(self, zahl):
while True:
if zahl < self.multible:
return False
elif zahl == self.multible:
return True
self.multible = self.multible + self.teiler
def prim_teiler_ohne_modulo(n):
if n < 3:
return [2] if n == 2 else []
PRIMZAHLEN = []
mroot = 0
for zahl in range(3,n,2):
for prim in PRIMZAHLEN[:mroot]:
if prim.mod(zahl):
break;
else:
PRIMZAHLEN.append(prim_modulo(zahl))
# Wenn n > 0 eine bekannte Natuerlichezahl und sqrt(n) bekannt ist, gibt es einen O(1) Weg um sqrt(n+1) zu berechnen ?.
mroot = int(len(PRIMZAHLEN) ** 0.5)
return [2] + [ m.teiler for m in PRIMZAHLEN ]
PS: Der Code ist von mir, das alternative Modulo Verfahren hab ich aber gestern Abend irgendwo im Internet gelesen, ich werde es heute Abend mal Verlinken.
PPS: Optimierungen an der prim_modulo Klasse sind willkommen.
