Geschrieben von Gast am 29.11.2010 um 12:14:
Primzahltest - Komplexität
HILFE,...
Ich habe eine Aufgabe zum Thema Primzahltest und Komplexität zu lösen bis morgen zu lösen und hab überhaupt keine ahnung...:
Z ist die Zahl, für die getestet werden soll, ob sie eine Primzahl ist.
n ist die Anzahl der Dezimalstellen (zb. 17 hat 2 Dezimalstellen).
Für jede Zahl T von 2 bis Wurzel Z wird geprüft, ob sie eine Primzahl ist, indem der Rest der Zahl Z durch T mit der Null verglichen wird (ist dieser Null, so ist ein Teiler von Z gefunden). Der Algorithmus endet, sobald ein Teiler gefunden wurde oder die Zahl eine Primzahl ist (also komplette Schleife durchlaufen).
Ich soll nun die Komplexität dieses Algorithmus in Abh. von den Dezimalstellen in O-Notation angeben (worst case, dh die Zahl Z ist eine Primzahl) und begründen, wie ich darauf gekommen bin...
Ich weiß, dass die Komplexität Wurzel Z wäre, aber ich darf sie nicht in Abh der Zahl sondern nur in Abh der Dezimalstellen (n) angeben...
könnt ihr mir vll helfen???
lg maya
