Primzahl

[infofa1]

Hallo,

ich brauche dringend Hilfe!!!
Das Programm soll die Primzahlen bis zu der eingegebnen Grenze in einer ListBox angeben.
als Vorlage haben wir folgendes

------------------

Delphi-Quellcode:

procedure TForm1.BRechnenClick(Sender: TObject);

var n, teiler, zahl   :integer;
    wurzel            :real;
    prim              :boolean;

begin
ListBox1.clear;
n:=strtoint(Edit1.text);
ListBox1.items.Add('2');
zahl:=3;

while zahl<=n do
 [COLOR="Red"]begin
  prim:=true;
  teiler:=zahl;
  wurzel:=sqrt(n);
 while (teiler <= wurzel) and (prim) do
   begin
    if zahl mod teiler:=0 then prim := false;
    teiler:=teiler + 1 ;
   end;[/COLOR]

if prim = True then
listbox1.Items.Add (inttostr(zahl));

end;

end.

--------------

ab der ersten while do Schleife ist es falsch. Aber was genau ???
Der Schluss stimmt auch wieder (if prim = True then
listbox1.Items.Add (inttostr(zahl)); )

Vielen Danke!

[madtom]

Hallo Infofa1,

erst einmal herzlich willkommen im Forum. :)
Zu Deinem Problem schau mal hier:

http://www.dbrsoftware.de/delphi/primz.php

Viel Spaß

madtom :)

[Reinhard Kern]

Zitat:

Zitat von infofa1 (Beitrag 1101388)

ab der ersten while do Schleife ist es falsch. Aber was genau ???

Hallo,

zahl muss hochgezählt werden (zahl := zahl + 1), sonst sind alle Schleifendurchläufe gleich und prüfen nur die Zahl 3. Und das endlos.

Gruss Reinhard

[infofa1]

Hallo madtom,

leider sind bin ich noch nicht mit den befehlen von deinem link vertraut.
die lösung müsste eigentlich nur mit den schleifen und den vorgegebnen var gehen.
das rot markierte ist ja nur falsch. aber ich komm nicht dahinter was alles ^^

fabi

[infofa1]

Zitat:

Zitat von Reinhard Kern (Beitrag 1101391)

Zitat:

Zitat von infofa1 (Beitrag 1101388)

ab der ersten while do Schleife ist es falsch. Aber was genau ???

Hallo,

zahl muss hochgezählt werden (zahl := zahl + 1), sonst sind alle Schleifendurchläufe gleich und prüfen nur die Zahl 3. Und das endlos.

Gruss Reinhard

In welcher zeile müsste ich das genau ändern?
eigentlich sollte nur im roten bereich die fehler sein^^

[Wolfgang Mix]

Delphi-Quellcode:

while zahl<=n do
begin
  prim:=true;
  teiler:=zahl;
  wurzel:=sqrt(n);
  while (teiler <= wurzel) and (prim) do
  begin
    if zahl mod teiler:=0 then prim := false;
    teiler:=teiler + 1 ;
  end;
  inc(zahl) //hier
end;

[infofa1]

Hallo Wolfgang Mix

danke schonmal

jetzt jedoch verlangt er dass der ausdruckstyp BOOLEAN sein muss in der zeile if zahl mod teiler:=0 then prim := false;
was stimmt hier noch nicht???

fabi

[Wolfgang Mix]

:= ist eine Zuweisung, Vergleiche brauchen nur das "=".
Laß mal den Doppelpunkt weg!

Delphi-Quellcode:

if zahl mod teiler=0 then prim := false;

[infofa1]

ahh nee
jetzt funktioniert es
aber er zeigt mir in der listbox bei n:=50 z.b.
nur 2 und 51 an ???

[Codewalker]

Zitat:

Zitat von infofa1 (Beitrag 1101398)

ahh nee
jetzt funktioniert es
aber er zeigt mir in der listbox bei n:=50 z.b.
nur 2 und 51 an ???

Was schließt du daraus? Die 2 fügst du manuell ein, es wird also nur die allerletzte Zahl ausgegeben. Du machst also erst NACH der Schleife eine Ausgabe und nicht bei jedem einzelnen Durchlauf. (Tipp: achte mal auf deine begin..end-s)

[infofa1]

habe jetzt folgendes:

var n, teiler, zahl :integer;
wurzel :real;
prim :boolean;

begin
ListBox1.clear;
n:=strtoint(Edit1.text);
ListBox1.items.Add('2');
zahl:=3;

while zahl<=n do
begin
prim:=true;
teiler:=zahl;
wurzel:=sqrt(n);
while (teiler <= wurzel) and (prim) do
begin
if zahl mod teiler=0 then prim := false;
teiler:=teiler + 1 ;
end;
if prim = True then
listbox1.Items.Add (inttostr(zahl));
zahl:=zahl+1;
end;
end;

------------------

anwendug läuft, zeigt mir jedoch in der listbox nur 2 und bei n z.b. 100 alle zahlen ab 11 bis 100 an
komme hier jetzt nicht weiter???

[infofa1]

ich habe jetzt die ausgabe aus der schleife genommen
geht trotzdem noch nicht

[Jumpy]

Du könntest einmal die Delphi-Tags (Römerhelm) benutzen, dann ist der Code besser lesbar.


wurzel:=sqrt(n);
würde ich vor die Schleife setzen, denn das muss nur einmal gesetzt werden (ist aber nicht das Problem).


teiler:=zahl;
muss
teiler:=1;
sein, da sonst in der Zeile mit mod immer direkt 0 rauskommt

[infofa1]

while zahl<=n do
begin
prim:=true;
teiler:=zahl;
wurzel:=sqrt(n);
while (teiler <= wurzel) and (prim) do
begin
if zahl mod teiler=0 then prim := false;
teiler:=teiler + 1 ;
end;
inc(zahl)
end;
if prim = True then
listbox1.Items.Add (inttostr(zahl));

habe wieder was besserers^^

jetzt kommt in der listbox aber nur 2 und 101 wenn ich n=100 eingeb
????

[infofa1]

Zitat:

Zitat von Jumpy (Beitrag 1101413)

Du könntest einmal die Delphi-Tags (Römerhelm) benutzen, dann ist der Code besser lesbar.


wurzel:=sqrt(n);
würde ich vor die Schleife setzen, denn das muss nur einmal gesetzt werden (ist aber nicht das Problem).


teiler:=zahl;
muss
teiler:=1;
sein, da sonst in der Zeile mit mod immer direkt 0 rauskommt

habe es jetzt so wie unten ohne teiler:=1

[Luckie]

Liest du eigentlich auch unsere Antworten? Guck doch mal, wo dein Listbox.Items.Add steht und wo die Primzahlen ermittelt werden.

[Aphton]

Komme dem zuerst bitte nach, was von dir verlangt wird - verpass deinem Code die schönen [delphi] Tags und rücke mal ordentlich ein!

Delphi-Quellcode:

  teiler:=zahl;
  {..}
  if zahl mod teiler=0 then
    prim := false;
  teiler := teiler + 1;

Ist dir eigentlich aufgefallen, dass die Abfrage immer True sein wird?
teiler erhält den Wert zahl. Nichts wird zwischenzeitlich geändert und anschließend wird geprüft, ob zahl dividiert durch teiler einen Rest liefert. Eine Zahl durch sich selbst liefert niemals nen Rest!
Deshalb ist bei dir prim immer false!

[infofa1]

Danke für eure Hilfe habs rausbekommen^^ :)

[infofa1]

Delphi-Quellcode:

procedure TForm1.BRechnenClick(Sender: TObject);

var n, teiler, zahl   :integer;
    wurzel            :real;
    prim              :boolean;

begin
ListBox1.clear;
n:=strtoint(Edit1.text);
ListBox1.items.Add('2');
zahl:=3;

while zahl<=n do
begin
  prim:=true;
  teiler:=2;
  wurzel:=sqrt(zahl);
  while (teiler <= wurzel) and (prim) do
  begin
    if zahl mod teiler=0  then prim := false;
    teiler:=teiler + 1 ;
  end;

if prim = True then
listbox1.Items.Add (inttostr(zahl));

zahl:=zahl+1;

end;
end;

end.

-> für die, dies noch interessiert

[DeddyH]

Abgesehen von der kreativen Einrückung solltest Du

Zitat:

Delphi-Quellcode:

if prim = True then

noch abändern in

Delphi-Quellcode:

if prim then

Sonst baust Du Dir nur unnötige Fehlerquellen ein.

[Jumpy]

Weitere Optimierung wäre:

teiler:=3;

in zusammenarbeit mit

zahl:=zahl+2;

und

teiler:=teiler+2;

So werden alle geraden Zahlen (>2) übersprungen, da sie ja eh nicht prim sind.

[Wolfgang Mix]

zusammengefasst:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var n, teiler, zahl :integer;
    wurzel :real;
    prim :boolean;
begin
  ListBox1.clear;
  n:=strtoint(Edit1.text);
  ListBox1.items.Add('2');
  zahl:=3;

  while zahl<=n do
  begin
    prim:=true;
    teiler:=3;
    wurzel:=sqrt(zahl);
    while (teiler <= wurzel) and (prim) do
    begin
      if zahl mod teiler=0 then prim := false;
      inc(teiler,2) ;
    end;

  if prim then
    listbox1.Items.Add (inttostr(zahl));
  inc(zahl,2);

  end;
end;

[implementation]

Eine andere Lösungsidee:

Man nehme ein Array of Boolean und befüllt es mit true.
Jetzt fängt man mit der 2 an (x := 2).
Und geht zunächst jedes zweite Feld durch und setzt es auf false.
Dann stehen arr[4], arr[6] usw. alle auf false.

Nun macht man mit der 3 weiter und schaut sich arr[3] an.
arr[3] ist true, also ist 3 eine Primzahl.
Nun geht man von hier aus wieder jedes dritte Feld durch und setzt es auf false.
Dann stehen arr[9], arr[15] und arr[21] ebenfalls auf false.

Nun die 4: arr[4] ist false -> keine Primzahl!

Weiter zur 5: arr[5] ist true -> Primzahl.
Wieder jedes fünfte Feld auf false setzen: Das wars dann wohl für arr[25] und arr[35].

Weiter zur 6: arr[6] ist false -> keine Primzahl!

Und immer so weiter.

[Coffeecoder]

Interessanter Lösungsansatz!
Man nennt dieses Verfahren das Sieb des Eratosthenes

Mfg Coffeecoder

[implementation]

Zitat:

Zitat von Coffeecoder (Beitrag 1101517)

Interessanter Lösungsansatz!
Man nennt dieses Verfahren das Sieb des Eratosthenes

Mfg Coffeecoder

Danke, ich wusste noch nicht, wie es heißt.

[sHoXx]

ich hab auch mal ein, halb fertiges aber eigentlich funktionsfähiges Primzahl-Programm gemacht,welches nach dem Sieb arbeitet. nicht schön aber selten, geb es euch mal als anhang mit

[Coffeecoder]

Sieht sehr gut aus!
Ich will aber kurz was "meckern" siehe Anhang. Absolute Pfade enden meistens böse :), denn sie sind nicht überall gleich ;)
Aber sonst find ich es gut :thumb:

Mfg Coffeecoder

[sHoXx]

gut da hab ich net dran gedacht, hatte nur kurz was dran ausprobiert :D

[Aphton]

Ich hab mal hier den Sieb des Erastothenes mit Unter- und Obergrenze implementiert.

Delphi-Quellcode:

type
  Int64Arr = Array of Int64;

function SieveOfErastothenes(lowerLimit, upperLimit: Int64): Int64Arr;
var
  SieveSize: Integer;
  Sieve: Array of Boolean;
  procedure _ValidateArgs();
  var
    x: Int64;
  begin
    if lowerLimit > upperLimit then
    begin
      x := lowerLimit;
      lowerLimit := upperLimit;
      upperlimit := x;
    end;
  end;
  procedure _Init();
  begin
    SieveSize := upperLimit - lowerLimit + 1;
    SetLength(Sieve, SieveSize);
    FillChar(Sieve[0], SieveSize, True);
  end;
  procedure _Sieve();
  var
    i, j, k: Int64;
  begin
    i := 2;
    while i < upperLimit do // eventuell unsichere Optimierung: i <= 2*SieveSize
    begin
      if i and 1 = 1 then
      begin
        if i >= lowerLimit then
          while (i < upperLimit) and (not Sieve[i-LowerLimit]) do inc(i);
        j := i;
        if j >= lowerLimit then inc(j, i);
        while j < lowerLimit do inc(j, i);
        while j <= upperLimit do
        begin
          Sieve[j-lowerLimit] := False;
          inc(j, i);
        end;
      end;
      inc(i);
    end;
  end;
  procedure _Pick();
  var
    i, j, k: Int64;
  begin
    i := 0;
    j := 0;
    SetLength(Result, SieveSize);
    while i < SieveSize do
    begin
      if Sieve[i] and ((lowerLimit+i) and 1 = 1) then
      begin
        Result[j] := lowerLimit+i;
        inc(j);
      end;
      inc(i);
    end;
    SetLength(Result, j);
  end;
begin
  _ValidateArgs();
  _Init();
  _Sieve();
  _Pick();
end;

Ein möglicher Aufruf:

Delphi-Quellcode:

var
  Primes: Int64Arr;
  i: Integer;
begin
  Primes := SieveOfErastothenes(100, 200);
  Memo1.Clear;
  for i := 0 to High(Primes) do
    Memo1.Lines.Add(IntToStr(Primes[i]));
end;

Dieser Aufruf - also der Aufruf mit den Argumenten 100 und 200 liefert die Primzahlen zwischen diesen Grenzen (Grenzen eingeschlossen!)

Edit:
Die äußerste Schleife in der _Sieb() Prozedur muss eigentlich nicht bis zu upperLimit durchlaufen werden. Es ginge auch weniger, nur muss ich grad überlegen, um wie viel weniger! (bis SieveSize?)

Edit2:
Habs nun mit

Delphi-Quellcode:

  while i <= 2*SieveSize do

ausgestestet und es hat funktioniert. Mathematisch kann ich es leider nich begründen!

Have fun!

[scrat1979]

Kann die Zeile

Delphi-Quellcode:

  if zahl mod teiler=0 then prim := false;

nicht noch optimiert werden in

Delphi-Quellcode:

prim := not (zahl mod teiler = 0);

??? Hab den Thread aber nur überflogen...

Grüsse,
SCRaT