Wie viele Primzahlen gibt es, die kleiner sind als n? |
| 25.11.2010, 11:50 | accxev | Auf diesen Beitrag antworten » |
| Wie viele Primzahlen gibt es, die kleiner sind als n? Hallo Matheboard! Im Zuge einer Arbeit, an der ich gerade sitze, möchte ich Zahlen über ihre Primfaktorzerlegung codieren. Also sprich: 12376 = 2^3 * 3^0 * 5^0 * 7^1 * 11^0 * 13^0 * 17^1 Nun codiere ich als String 3|0|0|1|0|0|1 Was ich jetzt suche ist, ist eine obere Schranke für die Länge der so codierten Strings. (diese Schranke sollte ideralerweise kleiner als O(log n) sein) Diese setzt sich zusammen aus einer Konstante für das wie auch immer umgesetzte | und der Anzahl der Primzahlen, die unter n liegen. Kennt jemand eine Vorschrift, die man hier verwenden könnte, oder weiß anderweitig Rat? Viele Dank schon mal im Vorraus! Meine Ideen: Eigene Ansätze habe ich leider noch nicht so wirklich, außer, dass die größte Primzahl die nächstkleinere zu n sein muss. Einen Zugang zu einer Primzahldatenbank und der Umgang mit "realistischen Zahlen" habe ich vorrausgesetzt, sonst müsste ich zu viel auf eventuelle Berechnungskomplexitäten rücksicht nehmen. Intuitiv würde ich auch sagen, dass es nicht mehr als Wurzel(n) Primzahlen sein werden, aber begründen, geschweige denn beweisen kann ich es bis jetzt nicht. |
||
| 25.11.2010, 11:55 | René Gruber | Auf diesen Beitrag antworten » |
Für die Anzahl der Primzahlen besagt der Primzahlsatz , d.h. im worst-case (eben wenn eine Primzahl ist) wird dein Tupel auch diese Länge von ungefähr haben. Das ist größer als , was dir vermutlich nicht gefallen wird, aber so ist es eben. |
||
| 25.11.2010, 12:03 | Booker | Auf diesen Beitrag antworten » |
| RE: Wie viele Primzahlen gibt es, die kleiner sind als n? Hallo, vielleicht hilft dir Wiki weiter: http://de.wikipedia.org/wiki/Primzahlsatz also: ist eine bessere Abschätzung. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
