Primzahltest

[sayuviech]

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

[Klotzkopp]

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

[sayuviech]

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

[Klotzkopp]

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.

[sayuviech]

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

[sayuviech]

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

[Klotzkopp]

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.

[sayuviech]

Vielen Dank :-)