Sieb des Eratosthenes: Wurzel

22.07.2011, 22:51

Keff91

Sieb des Eratosthenes: Wurzel

Hallo Leute,

habe eine Frage zur "Logik" hinter dem Sieb des Eratosthenes.
Ich denke es sollte bekannt sein, dass das Sieb alle Primzahlen $\begin{eqnarray*} \le N \end{eqnarray*}$ heraussiebt.
Man tut dies, indem man alle Vielfachen von 2 löscht, dann zur nächstübrigen Zahl 3 geht und alle Vielfachen löscht, dann zur nächstübrigen Zahl 5, usw.

Man kann aufhören, wenn man über $\begin{eqnarray*} \sqrt(N) \end{eqnarray*}$ hinweg ist.
Warum genau eigentlich?

Mfg

22.07.2011, 22:58

tigerbine

Auf diesen Beitrag antworten »

RE: Sieb des Eratosthenes: Wurzel
Was sucht man denn? Was macht das mit der Zahl? Wie schreibt man dann die Zahl? Nun eine Idee?

22.07.2011, 23:03

Keff91

Auf diesen Beitrag antworten »

RE: Sieb des Eratosthenes: Wurzel

Zitat:

Original von tigerbine
Was sucht man denn? Was macht das mit der Zahl? Wie schreibt man dann die Zahl? Nun eine Idee?

Sei $\begin{eqnarray*} x \end{eqnarray*}$ ein Vielfaches von $\begin{eqnarray*} k < \sqrt{N} \end{eqnarray*}$ .
$\begin{eqnarray*} x \end{eqnarray*}$ kann dann keine Primzahl sein und wird gelöscht.

Leider stehe ich auf dem Schlauch unglücklich

22.07.2011, 23:07

tigerbine

Auf diesen Beitrag antworten »

RE: Sieb des Eratosthenes: Wurzel
http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

Zitat:

erfahren, wie die Primzahlen zwischen 2 und 120 ermittelt werden: Erst werden alle Vielfachen von 2 gestrichen, dann alle Vielfachen von 3, 5, und 7. Die Markierungen beginnen jeweils mit dem Quadrat der Primzahl: 4, 9, 25, 49. Da bereits 112 = 121 nicht mehr im Wertebereich liegt, werden ab 11 keine zusammengesetzten Zahlen mehr markiert; alle noch unmarkierten Zahlen sind prim.

Die Zahlen müßten sich ja in bestimmter Weise faktorisieren lassen, und das geht eben nicht mehr.

22.07.2011, 23:18

Keff91

Auf diesen Beitrag antworten »

RE: Sieb des Eratosthenes: Wurzel
Freude