Bis zu welcher Zahl muss ich die Teilbarkeit überprüfen?
Sieb des Erathostenes. Es geht um alle Teiler der Zahl bis 100
3 Antworten
Sieb des Eratosthenes
Dabei geht es darum, die Primzahlen herauszufinden.
Schreibe alle Zahlen von 1 bis 100 als 10X10-Feld auf.
Dann umkreist du die 2 und streichst alle Vielfachen der 2 durch. Das machst Du dann mit allen anderen Zahlen auch. Die, die dann übrig bleiben, sind außer der 1 Primzahlen.
Für das Sieb des Eratosthenes genügt es, die Zahlen bis zur Wurzel aus 100 zu prüfen, also bis 10.
Wenn eine Zahl einen Teiler größer als 10 hat, dann hat sie auch mindestens einen Teiler kleiner als 10, so dass dieser Fall schon geprüft wurde. Z.B. 99 ist durch 11 teilbar, fliegt aber schon beim Test mit dem Teiler 9 raus, so dass 11 nicht mehr geprüft werden muss.
Ja, das reicht. Zwischen 8 und 10 gibt es ja keine Primzahlen.
Die Obergrenze 10 gilt für den Fall, dass man die Primzahlen noch nicht kennt, z.B. wenn das ein Rechnerprogramm werden soll.
Bis 100, wobei 1 und die Zahl selbst ja jede Zahl teilen.
100/101 kann ja gar nicht mehr glatt aufgehen, da nie 101 nicht ein einziges mal in 100 passt, also bei allen Zahlen x > 100 100/x < 1 wird
Also reicht es einfach bis zur Primzahl 7 zu prüfen?