Primzahlberechnung

Ich habe letztens etwas an einem Algorithmus gearbeitet der dazu dient Primzalhen, bzw. die Teiler einer Zahl die selbst natürliche Zahlen sind zu ermitteln(nur zwei Teiler heißt: es ist eine Primzahl).

Ich denke ich habe den Rechenaufwand auf eine Minimum reduziert, indem ich nurnoch die Teiler durchrechne die nicht größer sind als die Quadratwurzel der Zahl(die mir noch nichteinmal bekant sein muss). Bin mir aber nicht sicher ob nicht doch falsche Ergebnisse dabei Rauskommen können und für's Testen fehlt mir leider die Rechenpower.

Hier mein Algortihmus(im Fokus steht wie gesagt die Ermittlung der Teiler):

Varriablen:
l = Fragliche Primzahl
m = potentieller Teiler
n = Liste mit Teilern
o = Anzahl der Teiler

Wenn l gerade, zähle in der folgenden Schleife immer um eins hoch. Anderfalls um zwei

Beginne mit einer kopfgesteuerten Zählschleife, starte mit m=1. Stope wenn mm größer/gleich l ist:
Wenn l/m keinen Rest ergibt:
Speichere den Akuellen wert von m in n.
Speichere außerdem das Ergebniss von l/m in n
Zähle die o um zwei hoch
erhöhe m um zwei(ungerade Zahl) oder eins(gerade Zahl)
Wenn die Schleife zu ende ist, Prüfe ob mm gleich l ist(also m die genaue Quadratwuzel ist), wenn ja:
Speiche m in n und erhöhe o um eins

Wenn ich mich nicht komplett vertan habe sollte dieser Algorithmus alle möglichen natürlichen Zahlen herausgeben, durch die l ohne Rest teilbar ist. Wenn diese Anzahl nur zwei(1 und die Zahl selber) ist, handelt es sich um eine Primzahl.

Außerdem bin ich mir nicht ganz sicher ob Zahlen mit nur einer Ziffer(1,2,3,5 und 7) als Primzahlen gelten. Muss ich hier eine Sonderbehandlung einfügen? Als was zählen sie?

Danke schonmal für alle Antworten

_matze

Christopher G. schrieb:

Außerdem bin ich mir nicht ganz sicher ob Zahlen mit nur einer Ziffer(1,2,3,5 und 7) als Primzahlen gelten. Muss ich hier eine Sonderbehandlung einfügen? Als was zählen sie?

Danke schonmal für alle Antworten

2, 3, 5 und 7 sind natürlich Primzahlen. 1 nicht, denn sie ist nur durch 1 teilbar. Klingt komisch, ist aber so.

probedivision nennt man, glaub ich, dieses verfahren. es gibt noch mehr tricks zum zerstückeln von zahlen in teiler: http://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms
aber wenn du nur rausfinden willst, ob irgendwas (mit hoher wahrscheinlichkeit) eine primzahl ist, dann google mal nach 'miller-rabin test'.