Primzahl in Robo Pro ausrechnen

Alles rund um TX(T) und RoboPro, mit ft-Hard- und Software
Computing using original ft hard- and software
Forumsregeln
Bitte beachte die Forumsregeln!
Antworten
Zwergnase
Beiträge: 178
Registriert: 01 Nov 2010, 19:45
Wohnort: Düsseldorf
Kontaktdaten:

Primzahl in Robo Pro ausrechnen

Beitrag von Zwergnase » 25 Jan 2011, 20:03

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

thkais
Beiträge: 381
Registriert: 31 Okt 2010, 21:45

Re: Primzahl in Robo Pro ausrechnen

Beitrag von thkais » 25 Jan 2011, 22:11

Hallo,

vielleicht hilft DIr das weiter...?

http://de.wikipedia.org/wiki/Primzahltest
Gruß
Thomas

Benutzeravatar
Dirk Fox
ft:pedia-Herausgeber
Beiträge: 1832
Registriert: 01 Nov 2010, 00:49
Wohnort: Karlsruhe
Kontaktdaten:

Re: Primzahl in Robo Pro ausrechnen

Beitrag von Dirk Fox » 25 Jan 2011, 22:43

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

Antworten