Primzahlen...
Christina Tusche
ich suche einen Algorithmus, mit dem man das Programm alle Primzahlen von 1
bis n ausspucken lassen kann. Hab schon einige zeit geknobelt, aber
irgendwie sitze ich auf der Leitung. Kann mir jemand helfen?
Chris
ps: Danke
Claudio Nieder
>ich suche einen Algorithmus, mit dem man das Programm alle Primzahlen von 1
>bis n ausspucken lassen kann. Hab schon einige zeit geknobelt, aber
MODULE prim;
IMPORT Log,MathL;
CONST n=10000;
PROCEDURE do*;
VAR
sieb:ARRAY n DIV 2 OF BOOLEAN;
i:LONGINT;
k:LONGINT;
s:LONGINT;
BEGIN
(*
2 ist die einzig moegliche gerade Primzahl, und wird hier separat behandelt.
*)
IF n>=2 THEN
Log.Int(2);
END;
IF n>2 THEN
(*
sieb[i] steht fuer die Zahl 3+2*i;
Es werden nur noch die ungeraden Zahlen ab 3 betrachtet.
Erstmal alle als prim annehmen.
*)
FOR i:=0 TO (n DIV 2)-1 DO sieb[i]:=TRUE; END;
(*
Die moeglichen Teiler von Primzahlen bis n sind die ungeraden
Zahlen von 3 bis Wurzel(n).
*)
s:=ENTIER(MathL.sqrt(n));
FOR k:=3 TO s BY 2 DO
(*
Aus sieb werden alle ungeraden Zahlen herausgestrichen
die den Teiler k haben ausser k selbst.
Bsp. k=5. Herauszustrichen sind 15, 25, 35 etc.
Da sieb[i] fuer 3+2*i steht sind die indizes 6,11,16 etc.
*)
i:=((k-3) DIV 2)+k;
WHILE i<n DIV 2 DO
sieb[i]:=FALSE;
i:=i+k;
END;
END;
(*
Diejenigen Zellen von sieb, deren Wert nach dem herausstrichen
immer noch auf TRUE sind, sind die Primzahlen.
*)
FOR i:=0 TO (n DIV 2)-1 DO
IF sieb[i] THEN
Log.Int(3+2*i);
END;
END;
END;
END do;
END prim.
--
Claudio Nieder, Kanalweg 1, CH-8610 Uster, Tel +41 79 357 6743
yahoo messenger: claudionieder aim: claudionieder icq:42315212
mailto:pri...@claudio.ch http://www.claudio.ch
Andreas Gumtow
zum Thema "Primzahlen...":
> ich suche einen Algorithmus, mit dem man das Programm alle Primzahlen
> von 1 bis n ausspucken lassen kann. Hab schon einige zeit geknobelt,
> aber irgendwie sitze ich auf der Leitung. Kann mir jemand helfen?
Das laeuft auf ein Sieb hinaus. Aber um die Sache gleich zu beschleunigen
kann man ausnutzen, dass alle Primzahlen (leider nicht nur diese) von
folgender Form sind:
Primzahlen >= 5
a) (6 * n) + 1 oder (6 * n) - 1 mit n=natuerlicher Zahl
Primzahlen >= 3
b) (4 * m) + 1 oder (4 * m) - 1 mit m=natuerlicher Zahl
Teilersuche nur bis zur Wurzel.
damit spart man schon den Test auf ungerade Zahlen und viele Vielfache...
Also in Pseudocode:
WriteInt(2,5); (* 2 ist Primzahl *)
WriteLn;
WriteInt(3,5); (* 3 ist Primzahl *)
FOR i = 5 TO max BY 2 DO (* nur ungerade Zahlen *)
prim = TRUE;
IF ((i-1) MOD 6 = 0) OR ((i+1) MOD 6 = 0) THEN DO (* Test auf a *)
IF ((i-1) MOD 4 = 0) OR ((i+1) MOD 4 = 0) THEN DO (* Test auf b *)
FOR j = 3 TO INT(SQRT(i)) BY 2 DO (* Test auf Teiler
IF i MOD j = 0 THEN DO ungerade und >2
prim = FALSE bis zur Wurzel *)
BREAK; (* Abbruch wenn teilbar *)
END;
END;
END;
END;
IF prim THEN DO
WriteInt(i,5); (* war nicht teilbar, also Primzahl *)
WriteLn;
END;
END;
Damit geht es recht schnell. Das Verfahren eignet sich auch zu einem
Kurztest fuer beliebige eingegebene Zahlen, da durch die Tests a und b
bereits viele Zahlen herausfallen, die nicht Primzahl sein koennen.
--
** Dipl.-Finw. (FH) A. Gumtow **
Thomas Weigelt
das geht auf alle Fälle:
MODULE prime;
IMPORT Out,In,Utils, Float, Strings;
VAR speicher: ARRAY 15000 OF LONGINT;
PROCEDURE EndCheckIfPrime(ttn: LONGINT;VAR output: BOOLEAN);
VAR i : LONGINT;
u: LONGINT;
BEGIN
output:=TRUE;
i:=1;
u:=ttn-1;
IF ttn = 2 THEN
output:=TRUE;
END;
FOR i:=3 TO u DO
IF ttn DIV i = ttn / i THEN
output:= FALSE;
END;
IF ~output THEN
i:=u;
END;
END;
END EndCheckIfPrime;
PROCEDURE CheckIfPrime(ttn: LONGINT;VAR output: BOOLEAN);
BEGIN
output:=TRUE;
IF (ttn = 1) OR (ttn = 4) THEN
output:=FALSE;
END;
IF ~(ttn DIV 2 = ttn/2) & ~(ttn = 2) THEN
IF output=TRUE THEN
EndCheckIfPrime(ttn,output);
END;
ELSIF ttn = 2 THEN
output:=TRUE;
ELSE
output:=FALSE;
END;
END CheckIfPrime;
PROCEDURE ProgMain*();
VAR ttn: LONGINT;
VAR output,also: BOOLEAN;
VAR Min_Max: LONGINT;
VAR q,s, speicheNR: INTEGER;
VAR Prompt: ARRAY 64 OF CHAR;
VAR Prompt2: ARRAY 6 OF CHAR;
VAR Max, Min: ARRAY 11 OF CHAR;
VAR i, StartWert, EndWert: LONGINT;
BEGIN
Max:=' ';
Prompt:='Bitte geben Sie den Startwert zwischen 0 und ';
Prompt2:=' ein!';
Strings.Str(MAX(LONGINT),Max);
Strings.Append(Prompt,Max);
Strings.Append(Prompt,Prompt2);
Out.String(Prompt);Out.Ln;
In.Prompt('[DT: LongInt]');In.LongInt(StartWert);
IF StartWert<1 THEN StartWert:=2; END;
Max:=' ';
Prompt:='Bitte geben Sie den Endwert zwischen ';
Prompt2:=' ein!';
Strings.Str(StartWert,Min);
Strings.Append(Prompt,Min);
Strings.Append(Prompt,' und ');
Strings.Str(MAX(LONGINT),Max);
Strings.Append(Prompt,Max);
Strings.Append(Prompt,Prompt2);
Out.String(Prompt);Out.Ln;
In.Prompt('[DT: LongInt]');In.LongInt(EndWert);
i:=0;
FOR s:=1 TO 14999 DO
q:=0;
INC(q);
speicher[q]:=0;
END;
FOR i:=StartWert TO EndWert DO
INC(speicheNR);
ttn:= i;
q:=0;
also:=TRUE;
CheckIfPrime(ttn,output);
IF output THEN
Out.Ln;
Out.Int(ttn,10);Out.String(' PRIME!');
Out.Ln;
IF speicheNR > 14999 THEN
speicheNR := 1;
END;
speicher[speicheNR]:=ttn;
ELSE
Out.Ln;
Out.Int(ttn,10);Out.String(' NOT!');
Out.Ln;
END;
END;
END ProgMain;
END prime.
(* (C)'2001 Thomas Weigelt, Jena *)