fischertechnik community forum

Hallo
Ich möchte, das Robo Pro mir die Primzahlen 1 bis 100 ausrechnet. Gibt es zum ausrechnen irgend ein Algorithmus / Formel dafür?

Hallo,

vielleicht hilft DIr das weiter...?

http://de.wikipedia.org/wiki/Primzahltest

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