Delphi-PRAXiS

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)
-   Algorithmen, Datenstrukturen und Klassendesign (https://www.delphipraxis.net/78-algorithmen-datenstrukturen-und-klassendesign/)
-   -   Primzahl (https://www.delphipraxis.net/160525-primzahl.html)

infofa1 17. Mai 2011 18:29

Primzahl
 
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 17. Mai 2011 18:43

AW: Primzahl
 
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 17. Mai 2011 18:49

AW: Primzahl
 
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 17. Mai 2011 18:54

AW: Primzahl
 
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 17. Mai 2011 18:56

AW: Primzahl
 
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 17. Mai 2011 19:06

AW: Primzahl
 
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 17. Mai 2011 19:15

AW: Primzahl
 
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 17. Mai 2011 19:21

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

Delphi-Quellcode:
if zahl mod teiler=0 then prim := false;

infofa1 17. Mai 2011 19:25

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

Codewalker 17. Mai 2011 19:35

AW: Primzahl
 
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 17. Mai 2011 19:35

AW: Primzahl
 
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 17. Mai 2011 19:42

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

Jumpy 17. Mai 2011 19:55

AW: Primzahl
 
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 17. Mai 2011 20:03

AW: Primzahl
 
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 17. Mai 2011 20:21

AW: Primzahl
 
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 17. Mai 2011 20:22

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

Aphton 17. Mai 2011 20:24

AW: Primzahl
 
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 17. Mai 2011 21:24

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

infofa1 17. Mai 2011 21:28

AW: Primzahl
 
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 18. Mai 2011 08:09

AW: Primzahl
 
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 18. Mai 2011 08:50

AW: Primzahl
 
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 18. Mai 2011 12:26

AW: Primzahl
 
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 18. Mai 2011 13:53

AW: Primzahl
 
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 18. Mai 2011 14:02

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

Mfg Coffeecoder

implementation 18. Mai 2011 14:37

AW: Primzahl
 
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 18. Mai 2011 16:15

AW: Primzahl
 
Liste der Anhänge anzeigen (Anzahl: 1)
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 18. Mai 2011 16:59

AW: Primzahl
 
Liste der Anhänge anzeigen (Anzahl: 1)
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 18. Mai 2011 17:06

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

Aphton 18. Mai 2011 17:22

AW: Primzahl
 
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 18. Mai 2011 22:18

AW: Primzahl
 
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


Alle Zeitangaben in WEZ +1. Es ist jetzt 00:22 Uhr.

Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz