Primzahlenberechnung
Peter Schütt
gegeben ist eine LongInt - Zahl.
Berechnet werden sollen alle Primzahlen von 2 bis zu dieser LongInt-Zahl.
Ich habe es so gelöst:
Ich trage alle erhalten Primzahlen in eine Liste ein (vergleichbar mit
TList).
Von der nächsten zu untersuchenden Zahl errechne ich die Wurzel und
teste dann alle Primzahlen, die ich bisher habe, bis zu dieser Wurzel,
ob sie durch die zu untersuchende Zahl teilbar sind.
Das geht auch alles.
1. Frage : Ist das Verfahren optimal ?
2. Frage : Mit diesem Verfahren komme ich nur bis MaxListSize.
Wie komme ich bis MaxLongInt oder sogar bis "MaxComp" ?
3. Frage : Gibt es eine relativ schnelle Funktion
PrimzahlByNr ( ANr : LongInt ) : LongInt , bei der ich
bspw. für ANr = 200 die 200. Primzahl ausgegeben bekomme ?
Ciao
Peter Schütt
--
Juchhee, ich habe jetzt eine eigene Domain.
www.pstt.de
Schaut mal rein,
allerdings hat sie nur wenig mit Delphi oder Pascal zu tun....
Michael Keppler
01beacc7$fdc0e860
> 1. Frage : Ist das Verfahren optimal ?
Wenn Du mit optimal die Geschwindigkeit meinst, dann nein. Für die
Berechnung wirklich großer Primzahlen werden gänzlich andere Methoden
verwendet, die dann zwar nur mit einer gewissen Wahrscheinlichkeit (nahe 1)
eine Primzahl auch als solche erkennen, dafür aber sauschnell sind. Leider
kann ich Dir auch nicht genau sagen, wie das funktioniert.
Das was Du gemacht hast, heißt "Sieb des Erathostenes" (nicht schlagen, wenn
der Name nicht stimmt) und ist die bekannteste und einfachste Lösung.
In einer Mathematikzeitschrift hatte ich einmal eine Lösung gefunden, die
sich "inverses Sieb" nannte und einen ganzen Teil schneller war, dafür aber
für jede zu testende Zahl mindestens ein Bit Speicher brauchte. Damit konnte
ich auf einem 486-33 damals (ja, ja, lang ist's her) ca. 100.000 Primzahlen
pro Sekunde ermitteln. Leider war dann schon bei 8 MB Schluß. Außerdem wird
das Verfahren dann bei größeren Zahlen wieder irgendwann überproportional
langsam.
Na ja, lange Rede, kurzer Sinn: Wenn Du Dich ernsthaft damit
auseinandersetzen willst, da gibt es ganze Bücher, die sich um nichts
anderes als die schnelle Berechnung von Primzahlen oder die Berechnung
großer Primzaheln drehen. Schau halt mal in eine gut sortierte
(Uni-)Bibliothek.
Ciao, Michael.
Unknown
die sind da schnell und blickig - hat mir schon oft geholfen
Marco Lange
Michael Keppler <Michael...@bigfoot.com> schrieb in im Newsbeitrag: 7j2p57$7n3@TGZ3...
> Das was Du gemacht hast, heißt "Sieb des Erathostenes" (nicht schlagen, wenn
> der Name nicht stimmt) und ist die bekannteste und einfachste Lösung.
Nein, das ist nicht das Sieb des Erathotenes.
Denn er überprüft mit seinem Algorithmus z.B zuerst, ob die gegebene
Zahl durch 2 teilbar ist, bei 4 überprüft er das aber auch.
Beim Sieb des Erathostenes, vielen erstmal alle Vielfachen von
2, 3, 5, 7 weg...
> Na ja, lange Rede, kurzer Sinn: Wenn Du Dich ernsthaft damit
> auseinandersetzen willst, da gibt es ganze Bücher, die sich um nichts
> anderes als die schnelle Berechnung von Primzahlen oder die Berechnung
> großer Primzaheln drehen. Schau halt mal in eine gut sortierte
> (Uni-)Bibliothek.
Im Internet sollte auch einiges zu finden sein, versuchs doch mal
mit MetaGer: http://www.metager.de
CU,
Marco
--
****************************************************
* E-mail: marco...@gmx.de *
* Homepage: http://www.online.de/home/marcolange/ *
* ICQ: 35807782 *
****************************************************
Peter Schütt
> > Das was Du gemacht hast, heißt "Sieb des Erathostenes" (nicht schlagen,
wenn
> > der Name nicht stimmt) und ist die bekannteste und einfachste Lösung.
>
> Nein, das ist nicht das Sieb des Erathotenes.
> Denn er überprüft mit seinem Algorithmus z.B zuerst, ob die gegebene
> Zahl durch 2 teilbar ist, bei 4 überprüft er das aber auch.
habe.
> Beim Sieb des Erathostenes, vielen erstmal alle Vielfachen von
> 2, 3, 5, 7 weg...
Juergen Schwarze
wenn Du eine Uni-Bibliothek in der Nähe hast, dann wirf mal einen Blick
in das Buch 'Angewandte Kryptographie' von Bruce Schneier. Schneier geht
in einem Kapitel (zwar nicht sehr tiefschürfend, aber immerhin) auf die
Berechnung von Primzahlen ein. Hilfreich dürfte in diesem Zusammenhang
jedoch das sehr umfangreiche Literaturverzeichnis sein, das dir
entsprechende weitergehende Literatur nennt.
Jürgen
"Peter Schütt" schrieb:
[...]
> Berechnet werden sollen alle Primzahlen von 2 bis zu dieser LongInt-Zahl.
[...]
Heiko Nocon
wrote:
>Nein, das ist nicht das Sieb des Erathotenes.
Doch, ist es.
>Denn er überprüft mit seinem Algorithmus z.B zuerst, ob die gegebene
>Zahl durch 2 teilbar ist, bei 4 überprüft er das aber auch.
>Beim Sieb des Erathostenes, vielen erstmal alle Vielfachen von
>2, 3, 5, 7 weg...
Logisch, darin besteht ja das Prinzip des Siebs, ist eine Zahl durch
eine andere Primzahl teilbar, dann ist sie selber keine.
Die Sache, bestimmte Zahlen vor dem Abchecken der Liste vorhergehender
Primzahlen gleich auszusortieren ist nur 'ne Optimierung und hängt
stark vom verwendeten Zahlensystem ab. Im Dezimalsystem kannst du z.B.
von vornherein alle mehrstelligen Zahlen aussortieren, die auf
0,2,4,5,6,8 enden. Die kannst du genau deshalb aussortieren, weil bei
ihnen feststeht, daß sie sich durch andere Primzahlen (2,5) teilen
lassen.
Das ändert aber nichts daran, daß du das Sieb verwendest. Du
vermeidest nur unnötiges Abklappern der Primzahlliste durch Verwendung
der Teilbarkeitsregeln für ganze Zahlen. (Grundschulwissen).
MfG Heiko
Bernd Aldenhövel
"Peter Schütt" <sch...@sahler.de> wrote:
>gegeben ist eine LongInt - Zahl.
>Berechnet werden sollen alle Primzahlen von 2 bis zu dieser LongInt-Zahl.
Wenn mir zu wohl wird, spiele ich gerne mal mit Primzahlen rum. Das
von Dir beschriebene Verfahren habe ich vor ein paar Wochen mal in
Delphi implementiert, aber
- mit einem "Bitarray" für einige zigtausend boolesche Werte
- mit einer Datei, in welche die gefundenen Primzahlen in
aufsteigender Reihenfolge geschrieben werden.
Die Quellen sind gezippt ca. 6500 Byte groß, und Du erhälst sie auf
Anforderung per Email.
Optimal ist das Verfahren aber sicher noch nicht. Aber immerhin kommst
Du (zumindest theoretisch) damit auch bis MaxLongint.
Gruß, Bernd
Marco Lange
Peter Schütt <sch...@sahler.de> schrieb in im Newsbeitrag: 01beacfa$71b45e00$5814bec3@sahler...
> > Nein, das ist nicht das Sieb des Erathotenes.
> > Denn er überprüft mit seinem Algorithmus z.B zuerst, ob die gegebene
> > Zahl durch 2 teilbar ist, bei 4 überprüft er das aber auch.
> Nein, tue ich nicht, weil ich nur durch die Primzahlen prüfe, die ich schon
> habe.
OK, dann eben doch:
Sieb des Erathostenes.
Bernd Aldenhövel
Heiko...@t-online.de (Heiko Nocon) wrote:
>On Wed, 2 Jun 1999 12:46:05 +0200, "Marco Lange" <marco...@gmx.de>
>wrote:
>
>>Nein, das ist nicht das Sieb des Erathotenes.
>
>Doch, ist es.
Schade, daß ich den Mann nicht gekannt habe. Er könnte interessant
gewesen sein, wenn er Jahrtausende nach seinem Ableben Glaubenskämpfe
provoziert ;-)
>>Denn er überprüft mit seinem Algorithmus z.B zuerst, ob die gegebene
>>Zahl durch 2 teilbar ist, bei 4 überprüft er das aber auch.
>>Beim Sieb des Erathostenes, vielen erstmal alle Vielfachen von
>>2, 3, 5, 7 weg...
>
>Logisch, darin besteht ja das Prinzip des Siebs, ist eine Zahl durch
>eine andere Primzahl teilbar, dann ist sie selber keine.
AFAIK besteht die Optimierung nicht darin, *bestimmte* Zahlen
auszusortieren, indem man den Algorithmus entsprechend verkompliziert,
wie Heiko das schreibt, sondern der Witz ist - und das fehlt
anscheinend auch bei Peters Vorschlag -, eine Negativliste zu führen,
in der alle Vielfachen der bekannten Primzahlen drinstehen.
Pseudo-Pascalmäßig:
var KoenntePrimSein: array [2..100] of boolean;
for i...
KoenntePrimSein[i] := true; // Initialisierung
i := 2;
while i <= 100 do begin
for j := 2 to 100 / i do
KoenntePrimSein[i*j] := false; // Vielfache aussieben
i := (* nächste Zahl mit KoenntePrimSein[i] = true *)
end;
Die Negativliste besteht hier dann aus denjenige Zahlen k, für die
KoenntePrimSein[k] = false ist.
Hoffentlich fragt jetzt keiner, ob man denn ein array [2..MaxLongint]
of boolean vereinbaren kann. Ich hab's nicht ausprobiert <g>
Gernot Zander
in de.comp.lang.pascal.delphi Heiko Nocon <Heiko...@t-online.de> wrote:
> >Nein, das ist nicht das Sieb des Erathotenes.
> Doch, ist es.
Nein, aber es ist das "reverse".
> Logisch, darin besteht ja das Prinzip des Siebs, ist eine Zahl durch
> eine andere Primzahl teilbar, dann ist sie selber keine.
... und ihre Vielfachen auch nicht. Die setzt man also gleich
auf False, und muss sie nicht mehr prüfen, daher wird das
Ding so schnell, denn du musst nur addieren, nicht aber
dividieren (was immer viel langsamer ist).
> Die Sache, bestimmte Zahlen vor dem Abchecken der Liste vorhergehender
> Primzahlen gleich auszusortieren ist nur 'ne Optimierung und hängt
> stark vom verwendeten Zahlensystem ab. Im Dezimalsystem kannst du z.B.
> von vornherein alle mehrstelligen Zahlen aussortieren, die auf
> 0,2,4,5,6,8 enden. Die kannst du genau deshalb aussortieren, weil bei
> ihnen feststeht, daß sie sich durch andere Primzahlen (2,5) teilen
> lassen.
Und wenn du dann noch 3+3+3+... rechnest und die alle austrägst,
und dann 5+5+5... usw., bleiben am Schluss nur noch die Primzahlen
übrig. Das genau ist der Witz dabei.
mfg.
Gernot
--
<hi...@gmx.de> (Gernot Zander)
Die Ehe ist eine wunderbare Einrichtung, die zwei Menschen befaehigt,
gemeinsam Schwierigkeiten zu ertragen, die sie nie gehabt haetten,
wenn sie einander nicht geheiratet haetten. (Lucky Luke)
Alex B.
Hallo,
wenn mich mein Erinnerungsvermögen an den Informatik-LK nicht im Stich
läßt, dann kannst Du das Verfahren auch in der Weise optimieren, daß
Du nur die Zahlen überprüfst (ob es eine Primzahl ist), die +/-1 um
das Vielfache von 6 liegen; Ausnahme: 1 und 3.
Will heißen: 5 und 7 sind Primzahlen und sind +1 bzw. -1 eines
Vielfachen von 6. Das nächst Vielfache wäre 12. Du müßtest dann
testen, ob 11 und 13 Primzahlen sind (sie sind es).
Es sind jedoch nicht alle Zahlen, die +/-1 um dieses Vielfachen liegen
eine Primzahl (zB.: 25).
Dieses Verfahren macht die Suche zumindest schneller, zumindest
daaaamals mit einem 8088 und DOS 3.0 und Turbo Pascal 3.0/4.0
Bis dann
Alex B.
Michael Keppler
Gernot Zander <hi...@gmx.de> schrieb in im Newsbeitrag:
7j5v09$lg1$1...@scorpio.in-berlin.de...
> Nein, aber es ist das "reverse".
>
> > Logisch, darin besteht ja das Prinzip des Siebs, ist eine Zahl durch
> > eine andere Primzahl teilbar, dann ist sie selber keine.
>
> ... und ihre Vielfachen auch nicht. Die setzt man also gleich
> auf False, und muss sie nicht mehr prüfen, daher wird das
> Ding so schnell, denn du musst nur addieren, nicht aber
> dividieren (was immer viel langsamer ist).
>
> Und wenn du dann noch 3+3+3+... rechnest und die alle austrägst,
> und dann 5+5+5... usw., bleiben am Schluss nur noch die Primzahlen
> übrig. Das genau ist der Witz dabei.
Da erkenn ich doch genau das, was ich damals programmiert habe ! Danke für
den Tip.
Übrigens: In C war das damals mein Primzahlprogramm eine einzige Anweisung,
wobei die Zwischenergebnisse gleich immer auf die nächste Verarbeitungsebene
herausgegeben wurden. So etwas wünsche ich mir von Delphi immer, oder gibt
es das schon ??
Als trivialstes Beispiel eben A:=B:=C:=1; und ähnliche Geschichten...
Ciao, Michael.
Peter Schütt
> Und wenn du dann noch 3+3+3+... rechnest und die alle austrägst,
> und dann 5+5+5... usw., bleiben am Schluss nur noch die Primzahlen
> übrig. Das genau ist der Witz dabei.
wie will man so etwas realisieren, wenn man bis in den LongInt - Bereich
(oder noch höher) gehen will ?
Ciao
Peter Schütt
Urs Stotz
Peter Schütt schrieb in Nachricht
<01beacc7$fdc0e860$7214bec3@sahler>...
>Hallo,
>gegeben ist eine LongInt - Zahl.
>Berechnet werden sollen alle Primzahlen von 2 bis zu dieser
LongInt-Zahl.
>Ich habe es so gelöst:
>Ich trage alle erhalten Primzahlen in eine Liste ein (vergleichbar
mit
>TList).
>Von der nächsten zu untersuchenden Zahl errechne ich die Wurzel und
>teste dann alle Primzahlen, die ich bisher habe, bis zu dieser
Wurzel,
>ob sie durch die zu untersuchende Zahl teilbar sind.
>Das geht auch alles.
>1. Frage : Ist das Verfahren optimal ?
>2. Frage : Mit diesem Verfahren komme ich nur bis MaxListSize.
>Wie komme ich bis MaxLongInt oder sogar bis "MaxComp" ?
>3. Frage : Gibt es eine relativ schnelle Funktion
> PrimzahlByNr ( ANr : LongInt ) : LongInt , bei der ich
> bspw. für ANr = 200 die 200. Primzahl ausgegeben bekomme ?
>Ciao
> Peter Schütt
[..]
diese Frage wurde vor etwa 2 Monaten in
news:de.comp.lang.pascal.misc
diskutiert. Wenn es dich interessiert, kannst du in
www.deja.com/home_ps.shtml
suchen. Es wurde da ziemlich ausführlich diskutiert. Leider habe ich
es nicht weiter-
verfolgt, sonst könnte ich dir den Algo posten.
Trage Subject optimale Primzahlberechnung ein.
Tschüss
Urs
Joachim Mohr
Ich habe es so wie Du programmiert! Es ist kein Problem, damit die 20
000. Primzahl zu berechnen!
Schaue Die mal folgende Prozedur an!
procedure findenaechstePrimzahl;
var groesstePZ:longint;
function hatKeineTeiler:boolean; //Versuch, ob groesstePrimzahl
wirklich PZ ist, d.h.
//nicht durch bisherige PZ geteilt werden kann
//Prüfung:primzahl[j] Teiler von GroesstePrimzahl? bis
// primzahl[j]>Wurzel(groesstePrimzahl) <beide hoch
zwei ... s.u.
var j:integer;
begin
result:=true; //falls bis zur Wurzel alle Primzahlen
durchprobiert
for j:=1 to AnzahlDerPrimzahlenBisher do Begin //ist 3,5,7 ...
Teiler
if groesstePZ<primzahlen[j]*primzahlen[j] then exit;
if
abs(groesstePZ-int(GroesstePZ/primzahlen[j])*primzahlen[j])<1/2 then
Begin result:=false; exit End; //Teiler gefunden
End;
end;
begin
groesstePZ:=primzahlen[AnzahlDerPrimzahlenBisher]; //Größte
bisher gefundene PZ
repeat //In Prozeur, die diese aufruft, muß Beginkontr stehen!
inc(groesstePZ,2); //Eine noch groesserPZ wird gesucht, evl.
PZ-Zwilling
until hatkeineTeiler;
inc(AnzahlDerPrimzahlenBisher); //Jetzt gibt's eine PZ mehr
if length(primzahlen)<=AnzahlDerPrimzahlenBisher+1 then
setlength(primzahlen,AnzahlDerPrimzahlenBisher+1000); //dyn
Array
primzahlen[AnzahlDerPrimzahlenBisher]:=groesstePZ; //Neue größte
PZ
end;
Tobias Eberle
wrote:
Hi Alex,
>wenn mich mein Erinnerungsvermögen an den Informatik-LK nicht im Stich
Informatik-LK, wo gibts denn das?
Tschau, Tobias
--
Nicht nur fuer Programmierer: "Unsere Fehler von heute sichern uns unser Brot von morgen."
Alex B.
wrote:
>
>Informatik-LK, wo gibts denn das?
>
Hi Tobias,
den Informatik-LK (LK=Leistungskurs) gibt und gab es damals bei uns am
Gymnasium. 1987 war unser Gymnasium eines von drei Gym. in Deutschland
die so einen Leistungskurs angeboten haben. Heute dürften es bestimmt
mehr sein.
CU, Alex
Christian Kaestner
>Gymnasium. 1987 war unser Gymnasium eines von drei Gym. in Deutschland
>die so einen Leistungskurs angeboten haben. Heute dürften es bestimmt
>mehr sein.
Bei uns is das aus Mangel an Schülern und Lehrern noch nie zustande
gekommen. Nachdem jetzt noch ein Lehrer weggegeangen ist haben wir
noch einen Lehrer, der bei uns überhaupt in der Oberstufe Info
unterrichten darf, und der müsse sich im nächsten Jahr "Delphi mit den
Schülern zusammen beibringen" (Orginal Zitat).
So long
Christian
--
______________________________________________________________________
http://www.kaestnerpro.de
(meine Freewareprogramme, und Delphi-Bereich)
Tobias Eberle
wrote:
Hi Alex,
>>
>>Informatik-LK, wo gibts denn das?
>>
>
>den Informatik-LK (LK=Leistungskurs) gibt und gab es damals bei uns am
>Gymnasium. 1987 war unser Gymnasium eines von drei Gym. in Deutschland
>die so einen Leistungskurs angeboten haben. Heute dürften es bestimmt
>mehr sein.
Bei uns auf jeden Fall nicht. Ab nächsten Jahr gibts glaub ich nen Grundkurs
- mit Delphiprogrammierung.
Alex B.
B.) wrote:
...dann hatten wir wohl sehr günstige Voraussetzungen. Einen
Förderverein der die Computer finanziert hat, viele fähige Lehrer
(hier einen schönen Gruß an Herrn Swora und Herrn Persaud) und
interessierte Schüler (in meiner Stufe gab es damals zwei LK's).
Wahrscheinlich liegt es aber auch oft an den Lehrern. Wir haben uns
nähmlich ein Schuljahr mit Prolog beschäftigt.
Schade eigentlich, ich habe gedacht, daß mittlerweile mehr Schüler die
Möglichkeit hätten sich nicht nur mit Grundkurswissen zufrieden geben
zu müssen.
Gruß, Alex
Stephan Reichelt
^^^^^^^^ Bitte entferne das. Viele SPAM-Bots filtern sowas
schon automatisch raus. Lege Dir doch eine email-Adresse bei gmx zu und
leite die mails dann auf Deine geo-mail-adresse um. Vorteil: Immer
gleiche email-ad und kein SPAM mehr...
> ....dann hatten wir wohl sehr guenstige Voraussetzungen. Einen
> Foerderverein der die Computer finanziert hat, viele faehige Lehrer
> (hier einen schoenen Gruss an Herrn Swora und Herrn Persaud) und
> interessierte Schueler (in meiner Stufe gab es damals zwei LK's).
>
> Wahrscheinlich liegt es aber auch oft an den Lehrern. Wir haben uns
> naehmlich ein Schuljahr mit Prolog beschaeftigt.
>
> Schade eigentlich, ich habe gedacht, dass mittlerweile mehr Schueler die
> Moeglichkeit haetten sich nicht nur mit Grundkurswissen zufrieden geben
> zu muessen.
Das hatte ich auch gehofft. Als wir aber dies Jahr unsere Belegplaene
fuer die 11/12 ausfuellen mussten, musste ich auch feststellen, dass es
Informatik bei uns nur im Grundkurs gibt ("Einfuehrung in die
Objektorientierte Programmierung").
Was solls, sind (hoffentlich) leicht zu holende Punkte fuer's Abi...
CU, Stephan R.
--
Erst wenn der letzte Fluss vergiftet, der letzte Baum gefaellt
und das letze Tier getoetet ist, werdet ihr merken,
dass man Geld nicht essen kann.
- Weissagung der Cree -
Markus Becker
>Bei uns is das aus Mangel an Schülern und Lehrern noch nie zustande
>gekommen. Nachdem jetzt noch ein Lehrer weggegeangen ist haben wir
>noch einen Lehrer, der bei uns überhaupt in der Oberstufe Info
>unterrichten darf, und der müsse sich im nächsten Jahr "Delphi mit den
>Schülern zusammen beibringen" (Orginal Zitat).
Ist doch kein Problem. Auf dem Gebiet bringt man sich und anderen
ständig etwas bei. Delphi wird ja auch immer "neuer".
Wir hatten damals (Abi '86) eine "Computer-AG" und haben da
auf "Basis 108" Maschinen (Apple II-Clones) UCSD-Pascal
programmiert... Das waren Zeiten.
Markus