Hallo
Ich möchte, das Robo Pro mir die Primzahlen 1 bis 100 ausrechnet. Gibt es zum ausrechnen irgend ein Algorithmus / Formel dafür?
Primzahl in Robo Pro ausrechnen
Forumsregeln
Bitte beachte die Forumsregeln!
Bitte beachte die Forumsregeln!
Primzahl in Robo Pro ausrechnen
Viele Grüße,
Manuel Neumann
Manuel Neumann
Re: Primzahl in Robo Pro ausrechnen
Gruß
Thomas
Thomas
- Dirk Fox
- ft:pedia-Herausgeber
- Beiträge: 1832
- Registriert: 01 Nov 2010, 00:49
- Wohnort: Karlsruhe
- Kontaktdaten:
Re: Primzahl in Robo Pro ausrechnen
Hallo Manuel,
bei so kleinen Zahlen verwendet man das Sieb des Eratosthenes (findest Du auch über den Wikipedia-Link).
Der Algorithmus ist sehr einfach: Man beginnt mit der kleinsten Primzahl (2) und streicht aus der Tabelle aller 100 Zahlen alle Vielfachen.
Also: Erst alle geraden Zahlen streichen, dann alle Vielfachen von 3, 4 ist schon gestrichen, dann alle Vielfachen von 5, 6 ist schon gestrichen, usw.
Das musst Du fortsetzen bis zur Wurzel aus 100 - da 8 und 10 gerade sind und 9 ein Vielfaches von 3, ist 7 die letzte Zahl, deren Vielfache Du streichen musst.
Dann bleiben in der Tabelle nur Primzahlen übrig.
Es gibt eine sehr schöne Optimierung (von mir , findet sich nicht in Büchern): Beim Streichen der Vielfachen kannst Du mit dem Quadrat der Primzahl beginnen - also bei 2 mit 4, bei 3 mit 9 (denn 3x2 ist schon gestrichen), bei 5 mit 25 (denn 2x5, 3x5, und 2x2x5 sind bereits gestrichen), und bei 7 mit 49 (denn 2x7, 3x7, 2x2x7, 5x7, 2x3x7 sind bereits gestrichen). Das geht richtig fix.
Beste Grüße,
Dirk
bei so kleinen Zahlen verwendet man das Sieb des Eratosthenes (findest Du auch über den Wikipedia-Link).
Der Algorithmus ist sehr einfach: Man beginnt mit der kleinsten Primzahl (2) und streicht aus der Tabelle aller 100 Zahlen alle Vielfachen.
Also: Erst alle geraden Zahlen streichen, dann alle Vielfachen von 3, 4 ist schon gestrichen, dann alle Vielfachen von 5, 6 ist schon gestrichen, usw.
Das musst Du fortsetzen bis zur Wurzel aus 100 - da 8 und 10 gerade sind und 9 ein Vielfaches von 3, ist 7 die letzte Zahl, deren Vielfache Du streichen musst.
Dann bleiben in der Tabelle nur Primzahlen übrig.
Es gibt eine sehr schöne Optimierung (von mir , findet sich nicht in Büchern): Beim Streichen der Vielfachen kannst Du mit dem Quadrat der Primzahl beginnen - also bei 2 mit 4, bei 3 mit 9 (denn 3x2 ist schon gestrichen), bei 5 mit 25 (denn 2x5, 3x5, und 2x2x5 sind bereits gestrichen), und bei 7 mit 49 (denn 2x7, 3x7, 2x2x7, 5x7, 2x3x7 sind bereits gestrichen). Das geht richtig fix.
Beste Grüße,
Dirk