Rechnerorganisation[5]#7

[salami]

Hallo,
ja ich weiß, wir müssen es nicht morgen abgeben, aber hab trotzdem noch eine Frage.

Und zwar müssen wir bei Aufgabe 7 genug Speicherplatz reservieren, um alle Primzahlen von 3 bis k (dynamisch) zu speichern.

Hat jemand eine Idee, wie man am besten die Größe berechnet?
k/2 wäre eine Lösung, aber wohl sehr verschwenderisch, da ja nicht jede ungerade Zahl auch eine Primzahl ist.

Gibts da vielleicht eine Formel?

[Johann]

Kann sein, dass ich mich damit zu weit aus dem Fenster lehne, aber ich glaube gäbe es eine Formel die sagt, wie viele Primzahlen es von x..y gibt, würde jeder Zahlentheoretiker jubeln vor Freude, das sind nämlich ziemliche Biester

Nach dem Primzahlsatz von Carl Friedrich Gauß (1777-1855) gilt, dass die Anzahl der Primzahlen, die kleiner sind als eine Zahl n, ungefähr gleich n geteilt durch den Logarithmus von n ist. In Formeln: µ(n) ungefähr gleich n/log n.

Von: http://www.spiegel.de/wissenschaft/mens ... 96,00.html

[salami]

Ok, danke. Wollte ja auch nur eine obere Schranke, keine genaue Formel.
Logarithmus berechnen ist mir jetzt aber doch zu aufwendig, ich bleibe bei k/2

Edit
Ich sehe gerade, dass ich ja nicht die Primzahlen von 3 bis k ausgeben soll, sondern die ersten k Primzahlen ab 3. Ich sollte besser lesen.
Damit hat sich das Problem erledigt, man benötigt k Felder.

Damit dieser Thread nicht ganz sinnfrei ist noch ein Tipp:
Wenn ihr k Felder reservieren wollt, dann müsst ihr 4*k Bytes reservieren, weil ein Wort ja 4 Bytes lang ist.