Primzahlenprogramm

Diskussion zum Thema Programmierung unter DOS (Intel x86)
Antworten
J. Heise
Norton Commander
Beiträge: 111
Registriert: Do 11. Sep 2008, 19:39
Kontaktdaten:

Primzahlenprogramm

Beitrag von J. Heise »

Hallo,

ich habe vor ca. 10-15 Jahren in Basic ein Primzahlenprogramm geschrieben, mit dem ich im FidoNet (kennt das noch jemand?) gegen einige Assemblerprogrammierer angetreten bin. Aufgabe war: Primzahlen von 1 -1.000.000 zu berechnen und auf dem Bildschirm auszugeben. Ich wollte damals beweisen, dass man auch mit Basic schnelle Programme schreiben kann. Was soll ich sagen: Ich habe haushoch gewonnen, denn mein Proggi war um Faktoren!!! schneller. Leider habe ich mich seit diesem Zeitpunkt nicht mehr mit diesem Thema befasst. Deshalb wollte ich mal nachfragen, ob im Laufe der Zeit hier irgend jemand neue Ideen entwickelt hat oder sonstige Verbesserungsvorschläge hat? Das Programm und den Sourcecode in Basic + Pascal gibt es auf meiner HP unter Autorenprofil.

LG
J. Heise
DOSferatu
DOS-Übermensch
Beiträge: 1220
Registriert: Di 25. Sep 2007, 12:05
Kontaktdaten:

Beitrag von DOSferatu »

Ich hab damals was gemacht, wo ich so eine Art "Raster" benutzt habe, um bestimmte Zahlen von vorherein auszuschließen. Das Raster war 210 booleans groß (Hätt auch Bits nehmen können.) Ich habs dann so gemacht, daß ich ne Zahl erstmal durch 210 geteilt hab (also MOD 210), und den Teilungsrest geprüft, ob er in dem Raster erwähnt wird.
(Die 210 sind 2*3*5*7, die ersten 4 Primzahlen.)
Auf die Art konnte ich die meisten Zahlen von vornherein ausschließen. Achja. Und natürlich hab ich nach 2 nur die ungeraden geprüft...
Hab da noch mehr eingebaut gehabt. Jedenfalls brauchte ich immer nur die paar Zahlen, die nicht im "Raster" waren, testen.
Später wurde mir mal gesagt, daß man solche Raster "Das Sieb des Erathostenes" nennt. Wußte ich damals nicht. Hatte ich wohl dieselbe Idee wie Erathostenes...

Nachtrag: Achja, meins war in PASCAL.
elianda
DOS-Übermensch
Beiträge: 1150
Registriert: Mi 31. Jan 2007, 19:04
Wohnort: Halle
Kontaktdaten:

Beitrag von elianda »

Das Sieb des Erasthotenes ist dafuer die Standardmethode. Es ist vermutlich sogar irgendwo bewiesen, dass es am effizientesten ist.
Stellt sich damit nur die Frage einer effektiven Implementation.
Im einfachsten Fall nimmt man fuer das 'sieben' in einem Bitfeld eine Schleife mit Variable Schrittweite. In etwa so:

const anzahl=1000000;
var field : array[1..anzahl] of byte;
i,i1 : integer;
begin
// Initialisierung
field[1]:=1;
for i:=2 to anzahl do field:=0;
// Sieben
for i:=2 to anzahl div 2 do
for i1:=2 to anzahl div i do field[i*i1]:=1;
//ausgeben
for i:=1 to anzahl do if (field=0) writeln(i);

Wenn man sich nun anschaut was Rechenzeit kostet, ist das vor allem die Multiplikation i*i1. Das kann man aber umgehen, indem man einfach immer i aufaddiert, da im inneren Schleifenteil sich nur i1 aendert.
Ich habe noch nicht geschaut ob das aktuelle Compiler automatisch aufloesen und optimieren.
Diverse Retro-Computer vorhanden.
DOSferatu
DOS-Übermensch
Beiträge: 1220
Registriert: Di 25. Sep 2007, 12:05
Kontaktdaten:

Beitrag von DOSferatu »

Naja. Alsoals erstes hab ich wie gesagt dieses Bitfeld genommen. (Ich erstelle das, indem ich halt erst das ding auf 1 setze und dann jede 2., jede 3., jede 5. und jede 7. stelle wieder 0-setze (bei dem 210er Feld) Bei größeren Feldern gehts noch besser., war ja nur n Experiment.
Und als zweites hab ich, WENN eine Zahl durchs "Raster" kam, also MÖGLICHERWEISE eine Primzahl ist, dann von dieser die Quadratwurzel gezogen. Aus zwei Gründen: 1. wenn die Wurzel eine ganze Zahl ergibt, isses schonmal keine Primzahl. aber vor allem 2.: Wenn nicht, brauch nur prüfen, ob sie durch Zahlen bis zum abgerundeten Wurzelergebnis teilbar ist - denn die anderen Zahlen sind ja "gegenüber" der Wurzel - also von einem Faktorenpaar sozusagen der andere Faktor. Und wenn's durch den kleineren Faktor ganzzahlig teilbar ist, ergibt sich der größere und umgekehrt...
So'ne Wurzel kostet zwar auch Rechenzeit - aber bei kleinen Zahlen fällts nicht so ins Gewicht, weil es da ja nicht so viele Teilungsprüfungen (auf ganzzahlige Ergebnisse) gibt (ich teile halt mit MOD und wenn der Rest halt=0...) und bei großen Zahlen reduziert das Prüfen nur bis zur Wurzel eben die Anzahl Prüfungen.
Das war aber wie gesagt nur ein kleiner Test von mir gewesen, es gibt vielleicht noch effektivere Methoden. Und wenn ich mich ne Weile damit beschäftigen würde, käme ich noch auf andere Gesetzmäßigkeiten.
Ich habe mich auch mal damit beschäftigt, den Beweis zu führen, ob/daß Primzahlen, genau wie natürliche Zahlen unendlich sind, also es nicht irgendwo eine Stelle gibt, ab der es keine Primzahl mehr gibt. (Ich weiß nicht genau, könnte es sein, daß das die "Riemannsche Vermutung" ist? Will jetzt nix falsches sagen...)
J. Heise
Norton Commander
Beiträge: 111
Registriert: Do 11. Sep 2008, 19:39
Kontaktdaten:

Beitrag von J. Heise »

Hallo,

ich glaube, dass mein Algorithmus marginal anders aufgebaut ist. Leider kann ich den "Sieb" in Pascal nicht testen, da mein Pascal nicht mehr läuft. Bei meinem neuen Rechner musste ich es patchen, da das Division-durch-Null-Problem vorhanden war und seitdem wird irgend eine Library angemosert. Auf jeden Fall läuft es nicht mehr.

Mich würde mal interessieren, wie schnell so ein Sieb im Vergleich zu meiner Lösung läuft. Kann das mal jemand ausprobieren? Danke!

LG
J. Heise
Benutzeravatar
Dosenware
DOS-Gott
Beiträge: 3745
Registriert: Mi 24. Mai 2006, 20:29

Beitrag von Dosenware »

afair hatte ich damals einfach jede gefundene Primzahl in einer Liste gespeichert und als Teiler wiederverwendet... hatte nur den Nachteil das man immer von vorne (bei der 3, die 2 musste in der Liste stehen) anfangen musste, oder dem die ersten n Primzahlen uebergeben musste - und halt der immense Speicherverbrauch

brachte den Vorteil, dass bei großen Zahlen zwischen 2 Primzahlen viele andere Zahlen sind, die ich einfach auslassen kann.

letztlich laesst sich ja jede (nicht Prim-) Zahl als Produkt einer Primzahl mit einer natuerlichen Zahl darstellen...
Antworten