Sieb des Eratosthenes?

11.09.2004, 21:02	Remington Steele	Auf diesen Beitrag antworten »
Sieb des Eratosthenes? Meine Nerven ... mir hatte neulichjemand gezeigt, wie das geht am Bsp. bis 16. Nun muß ich aber alle Primzahlen bis 100 bestimmen, wie schreibe ich das hin? Ich habe alle Zahlen von 1-100 aufgeschrieben, 10 Zahlen pro Zeile. Irgendwie konnte man dann doch einfach die Diagonalen und Senkrechten wegstreichen, die von den Primzahlen bis Wurzel 100 = 10 ausgehen, doch wenn ich das mache, ergibt das irgendwie keinen Sinn, dann würde z.B. auch die 11 gestrichen. Wie macht man das nochmal? Danke...
11.09.2004, 22:35	mYthos	Auf diesen Beitrag antworten »
Das hat mit Diagonalen und Senkrechten nichts zu tun. Man geht einfach alle Primzahlen von vorne durch und streicht dann alle Vielfachen! Du beginnst mit 2, 2 bleibt stehen, streichst 4, 6, 8, ... usw., dann 3, 3 bleibt stehen, 6, 9, 12, 15, ... werden gestrichen, 5 bleibt stehen, 10, 15, 20, 25, ... kommen weg, usw. Man geht weiter bis zur nächsten noch nicht gestrichenen Zahl und streicht davon alle Vielfachen. Dabei muss man alle Zahlen bis 100 durchgehen, also nicht etwa bei 10 aufhören. Mit Hilfe dieses "Siebes" werden alle Nicht-Primzahlen ausgefiltert und es bleiben die Primzahlen über: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 Nur bis zur Wurzel aus einer Zahl muss man prüfen, wenn man die Teiler dieser Zahl bestimmen will. Hat diese Zahl bis zu ihrer Wurzel keine echten Teiler, so ist sie eine Primzahl. Bei 83 z. B. braucht man also nur bis 9 prüfen. Es sind 3, 5, 7, 9 keine Teiler, also ist sie prim. Gr mYthos
12.09.2004, 00:09	carsten	Auf diesen Beitrag antworten »
nur bis zur 10 streichen wenn ich alle Primzahlen bis 100 suche, dann reicht es bis (inklusive) 10 alle Vielfachen der ersten Zahlen aus der Auflistung zu streichen. Denn: wenn es eine Zahl zwischen 11 und 100 gaebe, die nicht prim ist und die ich noch nicht gestrichen habe, dann muessten alle ihre Primfaktoren groesser als 10 sein. Da die Zahl aber nicht prim ist, muss sie mindestens zwei Primfaktoren besitzen und damit ist sie groesser oder gleich 11*11=121, also ausserhalb unseres Bereiches. Das mit den Senrechten und Diagonalen habe ich noch nie gehoert, aber vielleicht hilft dieser Link: http://www.faust.fr.bw.schule.de/mhb/eratosib.htm weiter. Gruesse Carsten
12.09.2004, 10:35	mYthos	Auf diesen Beitrag antworten »
Es stimmt, thx carsten, man muss nicht alle Zahlen bis 100 durchgehen, wie auch der Link eindrucksvoll beweist. War mein Fehler. Wenn man die 11 erreicht hat, bleiben ohnehin nur noch alle Primzahlen bis 100 stehen. Gr mYthos
12.09.2004, 11:00	Remington Steele	Auf diesen Beitrag antworten »
Danke für die Info.. ... ach so, dann war das mit den Senkrechten / Diagonalen nur ein Trick. Wenn man eine 10x10 Auflistung hinschreibt, stehen nämlich unter der 2, 4 ,6, 8, und 10 alles Vielfache von 2... und Diagonal zu 3, 6, 9 usw. alles Vielfache von 3. Allerdings bleiben dennoch Zahlen übrig bei der 7, die man dann manuell löschen muß (z.B. 49). Wie ist das eigentlich bei ungeraden Zahlen, wenn ich z.B. 17 habe und die Wurzel 17 ziehen muß, um zu sehen, bis zu welcher Zahl ich die Primzahlen nachsehen muß... ist das dann die Wurzel 17 ab- oder aufgerundet?
12.09.2004, 13:28	mYthos	Auf diesen Beitrag antworten »
Du suchst einfach des (letzte) vollständige Quadrat kleiner als 17, es ist 16. Somit brauchst du nur bis 4 prüfen, denn $\begin{eqnarray} 5^2 \end{eqnarray}$ ist ja schon 25. Somit kannst du "abrunden". Bei 156 prüfst du beispielsweise bis 12 ( $\begin{eqnarray} 12^2 \end{eqnarray}$ = 144, $\begin{eqnarray} 13^2 \end{eqnarray}$ = 169).
Anzeige

12.09.2004, 14:45	Remington Steele	Auf diesen Beitrag antworten »
danke - dann wäre wohl alles klar .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »