Sieb des Eratosthenes
Christian Spannagel
https://www.youtube.com/watch?v=Cg8P4GNPe0I

Transkript (automatisch erstellt)

0:05 jetzt die Frage wie findet man eigentlich Primzahlen ich habe da mal was vorbereitet ja wie in der Super
0:21 Kochsendung hier zack Hool ich die Sache hier aus dem Herd raus alles schon gekocht
0:31 so wie findet man eigentlich [Musik] Primzahlen ich mE man kann jetzt
0:43 anfangen 2 3 5 7 11 13 17 19 bis zum bestimmten Punkt kommen wir alle noch ganz gut hin ne 19 was die nächste Primzahl 23 dann
0:53 kommt bitte 27 27 ist eine Primzahl nee ne 29 29 erstmal eine ne dann 31 was kommt dann
1:09 37 ja nein ja hö ich na ja gut irgendwann wird schwierig jetzt können sich vorstellen wenn sie in größeren Bereichen sind dann wird's richtig
1:18 schwierig ja danke schön das Sieb des eratostenes ich schreib es ihn mal an
1:39 ja Sieb des eratostenes bitte merken Sie sich wo das H
1:54 steht eratostenes wenn sie das schon genannt haben wissen Sie auch wie es funktioniert wo sind sie
2:11 ja alle vi dieah und so weiter genau also ich ich habe die eins erstmal nicht
2:22 hingeschrieben wir wollen Primzahlen finden eins ist definitiv kein also komen schon weglassen wir gucken alle natürlichen Zahlen größer als ein an so
2:28 jetzt nehme ich mir mal die erste Z die Z ist eine Primzahl jetzt nehme ich mir die und streiche alle vielfachen dieser Zahl Weg vielfache wegstreichen
2:38 heißt die können keine Primzahlen sein weil sie vielfacher ein der Primzahl sind also die vi kann keine sein die 6 kann keine sein kann keine sein 10 kann
2:46 keine sein 12 kann keine sein 14 nicht 16 nicht 18 nicht 20 nicht aha hier kriege ich jetzt schon irgendwie so gewisses
2:55 systemell ich habe schon Biss strukturiert aufgeschrieben das heiß stehen lauter Vielfache der zwei also kann ich doch die hier streichen weg
3:03 damit weg damit ja so hier stehen lauter Vielfache der Z alle gestrichen da stehen lauter Vielfache der zwei hier wieso habe ich denn hier aufgehört bei
3:16 45 46 47 bin ich vorin abgelenkt worden W eigentlich bis zur 50 gehen so so die weggestrichen die weggestrichen und hier hinten steh later
3:27 Vielfache der zwei so das können keine Primzahlen sein so jetzt geht mal einfach weiter vorne 3 jetzt streichen mal alle
3:37 vielfach in der 3 3 bleibt stehen 3 ist eine Primzahl offensichtlich ist die nächste Zahl dann eine Primzahl weil sie nicht gestrichen wurde und kein
3:45 Vielfaches einer Zahl ist die kleiner ist ja also ist 3 eine Primzahl also streichen wir die vielfach in der D 6 ist schon gestrichen okay müssen wir
3:53 nicht doppelt streichen ne ist ein Vielfaches der 3 12 schon gestrichen 15 ist ein Vielfaches der 3 18 schon gestrichen ja
4:05 logisch jedes ne jedes Vielfache der SE ist ja schon gestrichen weil wir die zwei mit dabei habten also 2 x 3 jedes jedes zweite Vielfache der 3 ist bereits
4:15 gestrichen also können wir die 18 nehmen und die 18 war gestrichen genau die 21 und jetzt aderen wir da mal 6 drauf 21 ist gestrichen 27 ist
4:28 gestrichen 33 streichen 39 streichen 45 streichen okay so alle
4:41 Vielfachen der drei sind gestrichen jetzt geht's weiter ne wir die fünf ne F F ist eine Primzahl weil sie noch
4:51 nicht gestrichen ist und kein Vielfaches einer kleineren Zahl fünf nehmen das müssen wir streichen die Zeh ist gestrichen
5:00 wegen 5 x 2 die 15 ist gestrichen wegen 5 x 3 die 20 ist gestrichen wegen 5 x 2 x 2 die 25 noch nicht ah ja 25 ist 5 x 5 haben wir noch nicht gestrichen könen
5:15 wir streichen so so die 30 ist schon gestrichen die 35 noch nicht 7 ja die K noch streichen 40
5:33 ist gestrichen 45 gestrichen 50 gestrichen fertig so die nächste Zahl jetzt nehmen wir die 7 alle Vielfachen der
5:45 7 7 14 21 28
5:55 55 42 49 ist noch nicht gestrichen 7 x 7 7 x 2 7 x 2 qu 7 x 3 und so weiter war all schon gestrichen 7 x 5 und so 7 x 7 noch nicht 49
6:08 streichen okay 11
6:20 oder nehmen wir mal 11 22 schon gestrichen 33 ist gestrichen 44 okay muss ich gar nichts mehr streichen aha gar nichts mehr
6:32 streichen die 13 13 26 schon gestrichen 39 schon gestrichen auch nichts mehr streichen komisch
6:45 17 34 schon gestrichen mus ich auch nichts mehr streichen 19 38 schon gestrichen mus ich auch nichts mehr streichen gar nicht
6:55 mehr streichen warum ist es so also ich verate was ich bin fertig ich kann aufhören nach der 7 kann ich
7:05 aufhören warum [Musik]
7:26 bitte die ne ist auch keine primzah genau ich müsste jetzt nach der 7 als nächstes die 11 nehmen warum muss ich die 11 nicht mehr nehmen ja weil das ja
7:35 alles vielfachte von den kleineren te also sprich 2 x 11 auch und so geht dann weiter und ja jetzt unter 50 werden wir keine
7:47 wenn es höher geht dann muss man ja auch noch die anderen berüichtigen wenn es höher geht muss man noch die anderen berücksichtigen genau wenn wir es bis
7:52 100 machen wollten hät wir die 11 noch nehmen müssen ja ne h wir die 11 auch nicht mehr nehmen müssen
8:01 wenn wir noch eine größere Zahl gehabt hätten die 1000 dann h wir die 11 nehmen müssen
8:09 ja bitte die zweite Stelle wiederholt sich die eine
8:23 Zahl ach so sie merken jetzt hier dass bei den bei Zahlen hinten immer eine 1 eine 3 eine 7 oder eine 9 steht oder eine F ne aber nur hier steht
8:35 eine fün also die zwei die fün s eine Ausnahme ansonsten haben hinten immer eine 3 eine 1 7 und eine 9 interessant aha aber es könnte doch eine dieser
8:46 Zahlen trotzdem noch eine Primzahl keine Primzahl sein oder haben alle Zahlen die 1 3 7 und 9 hinten haben sind das
8:54 Primzahlen nee ne welche z.B nicht 39 39 ist ist keine Primzahl auch n ne hinten na ja okay sie stellen also fest wenn ich eine Primzahl habe dann steht hinten
9:09 1 3 7 oder 9 als letzte Ziffer aber ich kann nicht schließen draus dass es umgedreht auch so ist ja also wenn ich eine Zahl habe wo hinten
9:19 eine 1 3 7 oder 9 als letzte Ziffer steht heißt es nicht automatisch dass es eine Primzahl ist wenn es aber nicht der Fall ist ist
9:27 es keine Primzahl klar ne weil alle bei den hinten 0 2 4 6 oder 8 steht sind der VI Vielfache von Z also gerade Zahlen und wenn hinten eine
9:38 F steht das ein Vielfaches von F kann ich auch ausschließen hat mit dem Dezimalsystem zu tun mit dem stellenwertssystem okay aber das war
9:47 nicht wirklich der Grund warum ich aufhören soll weil es könnte sein dass hier noch eine andere Primzahl drin ist ja wenn man die die größte Primzahl in
9:56 unserem Fall let multipliziert die 35 und wenn man die S mit sich selbst multipliziert die
10:06 49 die nächst größere brzahl der oder die nächst größere Zahl wo sich brzah finden würden W dann 11 x 11 oder die 11 x 7 49 unsere
10:19 größte Zahl ist gen ja das ist sehr geht absolut in die richtige Richtung richtig sie haben die die S haben als letztes genommen da
10:29 haben wir Lette Malus gestrichen 7 x 7 ist 49 die Zahl haben wir als letztes gestrichen wenn ich jetzt die 11 nehme da müsste die 11 mit einer Zahl
10:41 multipliziert ja irgendeine Zahl geben die kleiner ist als 50 damit ich die streichen kann diese Zahl müsste kleiner sein als
10:53 11 11 x 11 ist größer als 50 also wenn ich eine Zahl mit 11 multipliziere sass potentiell noch eine zu streichende Zahl hier rauskommt dann
11:05 müsste ich die 11 mit einer kleineren Zahl als 11 multiplizieren das habe ich ja aber alles schon gemacht 11 x 2 11 x 3 11 x 5 11 mal und so weiter habe ich
11:15 doch allees schon gestrichen der Punkt ist wenn sie in komplementärteilern denken wenn ich einen Teiler
11:26 habe der wenn hier ist mein n = 50 wenn ich einen Teiler habe der kleiner ist als Wurzel
11:38 n dann ist der komplementärteiler größer als Wurzel n damit beides zusammen n ergibt also wenn ich Wurzel n habe dann ist Wurzel n mal
11:49 wurel n ja g= n wenn ich diesen einen Teiler kleiner mache als Wurzel n dann muss der andere größer sein als Wurzel n damit beides wieder n ergibt
12:00 oder wenn ich einen kleiner mache als Wurzel n und anderen so belasse dann bin ich kleiner als n wenn aber ein Teiler größer ist als
12:11 Wurzel n dann muss der andere auf jeden Fall kleiner sein als Wurzel n damit eine Zahl kleiner gleich n rauskommt wenn ich also Streiche dann
12:23 nehme ich alle Zahlen die kleiner sind als Wurzel 50 alle Zahlen bis zur Wurzel aus 50 oder
12:33 na sagen mal Wurzel aus 49 ist die 7 ja also alle Zahlen bis zur Wurzel weil die komplementärteiler dann oder multipliziert mit die komplementärteiler
12:44 die potentiell noch größer als die Wurzel n sein können multipliziert dann maximal 50 ergeben sobald ich über die Wurzel n rüber
12:54 geschritten bin sobald ich über die S hier rüber geschritten bin bräuchte ich für die 11 einen elärteiler der kleiner ist als Wurzel
13:02 n und die habe ich ja alle schon berücksichtigt es kann kein Vielfaches dieser mehr zu streichen sein das heißt ich gehe mit dem Sieb des eratossenes
13:13 immer bis Wurzel aus n also bis zur Wurzel der Endzahl
13:28 okay so jetzt eine Frage die man sich stellt wenn man mit Primzahlen
13:40 arbeitet wie viele gibt's überhaupt gibt's unendlich viele oder gibt es
13:50 irgendwo eine größte Primzahl [Musik] Schule hier werden Zettelchen
14:01 rumgereicht was steht denn drauf gehen Sie mal her willst du mit mir gehen ja nein
14:21 vielleicht es gibt unendlich viele Primzahlen man wird keine größte finden D wird es gibt immer noch eine größere
14:30 jetzt kann s überlegen woher weiß man das ja woher weiß man das mein so ausprobieren kann ich z.B mit dem Sieb des eratostenes nur bis zu
14:43 einer endlichen zahl ich kann noch eine größere nehmen bis dahin streichen noch eine größere bis dahin streichen so weiter aber ich werde nie sicher sein
14:51 dass ich nicht da schon die letzte Primzahl drin gefunden habe