Primzahlenberechnung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:43 Mi 13.04.2011 | | Autor: | weaser08 |
Hallo,
ich möchte das Verfahren "Sieb des Eratosthenes" in einer Programmiersprache umsetzen.
Hier eine kurze Einführung:
"Das bekannteste Verfahren zur systematischen Berechnung aller Primzahlen in einem Intervall von 2 bis zu einer Schranke n ist wohl das Sieb des Eratosthenes. Es beruht darauf, daß man aus einer Liste aller Zahlen von 2 bis n, bei der kleinsten Primzahl beginnend, die Vielfachen der Primzahlen streicht, bis nur noch Primzahlen in der Liste stehen. Wenn man hierbei die größte Primzahl abgearbeitet hat, die kleiner als die Quadratwurzel von n ist, ist man auch schon fertig."
Warum muss man nur die größte Primzahl, die kleiner als die Quadratwurzel von n ist abarbeiten?
Meine Vermutung:
Durch Multiplikation aller Kombinationen der Primzahlen, die die kleiner als die Quadratwurzel von n sind, können alle zahlen < n, die nicht Primzahl sind, berechnet werden?
Könnte das auch jemand irgendwie Formal darstellen und etwas anschaulicher beschreiben, bzw ist meine Vermutung vollständig..:)?
Besten Dank!
LG
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:03 Mi 13.04.2011 | | Autor: | novex |
Also meiner meinung nach hast du den Algorithmus ja verstanden...woran liegt es dann das du es nicht programmieren kannst ?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:39 Mi 13.04.2011 | | Autor: | weaser08 |
Der Algorithmus ist ja schon umgesetzt!
Wollte nur sicher gehen, dass ich die Anweisung:
"Wenn man hierbei die größte Primzahl abgearbeitet hat, die kleiner als die Quadratwurzel von n ist, ist man auch schon fertig."
auch wirklich verstanden habe und richtig begründen kann, warum das gerade so gemacht werden muss, bzw. warum es sinnvoller ist.
Meine Vermutung:
Durch Multiplikation aller Kombinationen der Primzahlen, die die kleiner als die Quadratwurzel von n sind, können alle zahlen < n, die nicht Primzahl sind, berechnet werden.
Ich wollte nun wissen, ob meine Vermutung richtig begründet ist!?
Gruß
|
|
|
| |
|
Hallo weaser08,
> ich möchte das Verfahren "Sieb des Eratosthenes" in einer
> Programmiersprache umsetzen.
>
> Hier eine kurze Einführung:
> "Das bekannteste Verfahren zur systematischen Berechnung
> aller Primzahlen in einem Intervall von 2 bis zu einer
> Schranke n ist wohl das Sieb des Eratosthenes. Es beruht
> darauf, daß man aus einer Liste aller Zahlen von 2 bis n,
> bei der kleinsten Primzahl beginnend, die Vielfachen der
> Primzahlen streicht, bis nur noch Primzahlen in der Liste
> stehen. Wenn man hierbei die größte Primzahl abgearbeitet
> hat, die kleiner als die Quadratwurzel von n ist, ist man
> auch schon fertig."
>
> Warum muss man nur die größte Primzahl, die kleiner als
> die Quadratwurzel von n ist abarbeiten?
>
> Meine Vermutung:
> Durch Multiplikation aller Kombinationen der Primzahlen,
> die die kleiner als die Quadratwurzel von n sind, können
> alle zahlen < n, die nicht Primzahl sind, berechnet
> werden?
Ja, richtig.
> Könnte das auch jemand irgendwie Formal darstellen und
> etwas anschaulicher beschreiben, bzw ist meine Vermutung
> vollständig..:)?
Das ist ziemlich einfach. Wenn Du eine Zahl n in zwei Faktoren p und q zerlegst, und [mm] p>\wurzel{n} [/mm] ist, dann muss [mm] q<\wurzel{n} [/mm] sein. Wenn man also alle möglichen Faktoren [mm] q<\wurzel{n} [/mm] bereits untersucht hat, kann es für [mm] p>\wurzel{n} [/mm] keine neuen Erkenntnisse mehr geben.
Klar?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:06 Mi 13.04.2011 | | Autor: | weaser08 |
Super danke, genau danach habe ich gesucht!
Gruß
weaser
|
|
|
|
