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

Die Anzahl der Stellen einer Zahl ist proportional zu ihrem Logarithmus.

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...

und das heißt???

Das ist der Zusammenhang zwischen n und Z, der dir offenbar fehlt.

Dein Algorithmus braucht offenbar Wurzel(Z) Operationen.

Jetzt ersetzt du das Z durch einen passenden Ausdruck, der n enthält, und dann hast du's doch schon.

Das ist der Zusammenhang zwischen n und Z, der dir offenbar fehlt.

Dein Algorithmus braucht offenbar Wurzel(Z) Operationen.

Jetzt ersetzt du das Z durch einen passenden Ausdruck, der n enthält, und dann hast du's doch schon.

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...

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...

jetzt muss ich mir nurnoch überlegen, wie ich die 10^n begründe...

10^n ist eine obere Schranke für eine n-stellige Zahl, denn 10^n ist die kleinste n+1-stellige Zahl.

Vielen Dank :-)