Programmieren - alles kontrollieren 4.939 Themen, 20.672 Beiträge

Primzahlen Programm mit Turbo Pascal

ZEPH / 10 Antworten / Flachansicht Nickles

Hi Folks!
ich hab in Computertechnik in der schule die aufgabe bekommen ein Prog zu schreiben, das die Primzahlen bis 20000 ausrechnet und anzeigt. ich darf die zahlen 2/3/5/7 als teiler vordefinieren, ab da muss alles andere selbst ausgerechnet werden. die primzahlen sollen in einem array gespeichert werden.
ich hab mir gedacht, dass ich eine variable(x) erhöhe und diese durch die im array gespeicherten zahlen teile und dann auf einen rest prüfe (mit "mod"). wenn der rest dann =0 ist wird die zahl im array gespeichert, und neu begonnen. das so lange bis x=20000.

geht denn das so wie ich es mir gedacht habe oder habt ihr eine leichtere (muss aber auch leicht verständlich bleiben ich hab TP erst seit einem halben jahr), Lösung?!

Schonmal Danke im vorraus für eure Mühen...

bei Antwort benachrichtigen
Andreas42 ZEPH „Primzahlen Programm mit Turbo Pascal“
Optionen

Hi!

Das geht, ist aber warscheinlich keine schnelle Lösung, da für alle Zahlenwerte deiner Variable(x) mehrere Rechenoperationen durchführen musst.

Tipp: programmiere es, das ist für Vergleichszwecke gut!

Du musst natürlich die 0-Modulo Ergebnisse der Divisionen zählen. Wenn diese Zahö >1 ist, dann hast du keine Primzahl (die Zahl war ja dann durch mehrer Werte teilbar).

Die bekannte Alternative ist (glaube ich) der Sieb des Aristoteles:

Nimm einen Array.
Nimm eine Zählvariable.
Beginne mit Zählvariable 3.
:loop
Belege alle Vielfachen der Zählvariablen im Array.
Erhöhe Zählvariable um 2.
Wenn Zählvariable kleiner Anzahl-Arrayelemente/2 dann :loop

Zum schluss erhält man einen Array, dessen Felder für Zahlen, die keine Primzahlen sind gefüllt sind. Die Leeren Felder sind dann Primzahlen (gerade Zahlen lässt man weg).

Ach ja: das kann man noch optimieren. Da war was mit neuen Zählvariablen, die schon im Array belegt wurden. ;-)

Bis denn
Andreas

PS: Programmier beides und vergleiche mal die Laufzeit.

Hier steht was ueber mein altes Hard- und Softwaregedoens.
bei Antwort benachrichtigen