sayuviech

Vielen Dank :-)

ich glaube ich habs: Wurzel (10^n), also 10^(n/2) liefert genau die Werte die ich brauche jetzt muss ich mir nurnoch überlegen, wie ich die 10^n begründe...

genau das ist mein problem... ich habe keine ahnung was ich stattdessen angeben könnte... wuzel Z hatte ich zunächst auch, aber ich darf die laufzeit leider nicht in abh von der zahl angeben, sondern nur in abh ihrer dezimalstellen...

und das heißt??? ich habe mir schon überlegt, dass vielleicht O(n) = 10^n sein könnte... aber ich weiß nicht, ob das stimmt und wenn ja, wieso...

Guten Morgen, Ich habe eine Aufgabe zum Thema Primzahltest und Komplexität zu lösen: 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). Ich soll nun die Komplexität dieses Algorithmus in Abh. von den Dezimalstellen in O-Notation angeben 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