Primzahlen

[Romiox]

Hallo zusammen!

Ich hab hier ein Stück Code das nicht macht was es soll, und so langsam glaub ich, dass ich gedanklich festgefahren bin.
Ich weiss, es gibt hier viele Threads zu dem Thema, aber erstens habe ich so meine Probleme anderer Leute Code zu lesen (Übungssache, nehm ich an^^)
und zweitens interessiert mich eigentlich mehr woran genau mein Code krankt, weniger der eigentlich Lösungsweg ;)

Delphi-Quellcode:

function isprime (a: integer): integer;   //soll testen ob a eine Primzahl ist
var
    b,i: integer;
begin
    if a <= 1 then                       // schließt erstmal 0, 1 und negative aus (einfacher ^^)
        isprime:=0
    else
        begin 
        b:=a;
        isprime:=1;                      // setzt den Rückgabewert auf 1 (ist eine Primzahl)
        while b > 1 do
            begin
            b:=b-1;
            i:= a mod b;
            if i = 0 then                // setzt den Rückgabewert wieder auf null (ist keine Primzahl) wenn ohne Rest teilbar
                isprime=0
            end
        end
end;

BTW; sollte ich als Rückgabe einen Boolschen Wert nehmen? Setz ich den dann auf 0/1 oder auf True/False?

Ich bin dankbar für jeden Kommentar zum Thema, hauptsächlich will ich aber wissen was ich falsch gemacht hab, nicht wies richtig geht :)

[DeddyH]

Hallo und Willkommen in der DP :dp:,

Boolean als Rückgabewert wäre wirklich angebrachter, da es ja nur 2 Möglichkeiten gibt. Dein Fehler ist, dass die Schleife auch dann weiterläuft, wenn das Ergebnis bereits feststeht, dadurch wird dieses wieder überschrieben.

[Romiox]

Danke für die schnelle Antwort :) ( :dp: /agree )

Ich bin nicht überzeugt ^^
Mal abgesehen von der Tatsache, das die Rückgabe Boolean sein sollte.

Mein Problem ist, das mir das Programm so immer 0 zurückgibt. Ja, die Schleife läuft weiter
(nicht unbedingt effektiv.. Jaja :) ) aber würde ja maximal wieder eine 0 setzen, das Ergebnis also
nicht verändern. Mein erster Gedanke war, das er noch durch 1 teilt, aber eigentlich sollte der Algorithmus
vorher terminieren (

Delphi-Quellcode:

while b > 1

).

Zum Thema Abbruch: Ein exit innerhalb der if-Verzweigung würde nur die Funktion abbrechen und den festgelegtenm Wert zurückgeben, oder?

[ho.sch]

Dein while-Konstrukt wird einmal zu oft durchlaufen. Für den Durchlauf mit b=2 bekommst Du dann immer eine nicht-prime Zahl gemeldet, weil Du danach ja noch 1 subtrahierst ...

[Romiox]

Hmm, :headdesk: gibts nicht? :lol:

Ja, danke. War meine Überlegung nicht so falsch, nur nicht ganz konsequent.

Danke auch beiden!

[DeddyH]

Stimmt, hast Recht. Beim Debuggen ist es mir aufgefallen: Du hast als Bedingung b > 1, ziehst aber innerhalb der Schleife wieder 1 ab, so dass Du immer durch 1 teilst.

[edit] Wo war der rote Kasten? [/edit]

[Romiox]

Roter Kasten? *confused*

Aber dank euch ists jetzt Version 1.1 ;D

[DeddyH]

[OT] Der rote Kasten kommt normalerweise, wenn Du einen Beitrag senden willst, nachdem zwischenzeitlich bereits anderweitig im Thread geantwortet wurde. Du kannst dann überprüfen, ob Du wirklich noch neue Inhalte beisteuern kannst. [/OT]

[edit] Ich konnte es nicht lassen und habe Deine Funktion einmal etwas verkürzt:

Delphi-Quellcode:

function isprime(a: integer): Boolean; //soll testen ob a eine Primzahl ist
var Teiler: integer;
begin
  Result := a > 1;
  Teiler := Pred(a);
  while Result and (Teiler > 1) do
    begin
      Result := a mod Teiler <> 0;
      dec(Teiler);
    end;
end;

[/edit]

[generic]

btw. auf dem T-Shirt was auf dem Delphi-Tagen 2010 verteilt wurde, ist etwas Quelltext, der Primzahlen berechnet - das sogar multithreaded.

[implementation]

Zitat:

Zitat von Romiox (Beitrag 1055814)

Hmm, :headdesk: gibts nicht?

Meinst du :wall:?

[Romiox]

Zitat:

Zitat von DeddyH (Beitrag 1055817)

Ich konnte es nicht lassen und habe Deine Funktion einmal etwas verkürzt:

Delphi-Quellcode:

function isprime(a: integer): Boolean; //soll testen ob a eine Primzahl ist
var Teiler: integer;
begin
  Result := a > 1;
  Teiler := Pred(a);
  while Result and (Teiler > 1) do
    begin
      Result := a mod Teiler <> 0;
      dec(Teiler);
    end;
end;

Danke, ich werd das mal nachvollziehen. :) Bin grad erst angefangen (Informatik 11.1),
hab noch nicht so'n großes Repertoire an Funktionen :)

Zitat:

Zitat von implementation (Beitrag 1055827)

Zitat:

Zitat von Romiox (Beitrag 1055814)

Hmm, :headdesk: gibts nicht?

Meinst du :wall:?

Noe, schon Desk. Aber :wall: tuts genauso :>

[Aphton]

Um bei deinem Code zu bleiben und weiters da du noch am Lernen der Sprache bist, hier ein paar nützliche Tipps

Delphi-Quellcode:

function IsPrime(a: integer): Boolean;
var
  b, i: integer;
begin
  if a <= 1 then
    Result := False // Anmerkung: Result entspricht "IsPrime" (Funktionsname) und ist somit der Rückgabewert (hence result!)
  else
  begin
    b := a;
    Result := True;
    while b > 2 do // hier lag der Fehler, der dir ja schon aufgefallen ist...
    begin
      b := b - 1;
      i := a mod b;
      if i = 0 then // setzt den Rückgabewert wieder auf null (ist keine Primzahl) wenn ohne Rest teilbar
      begin
        Result := False;
        Break; // break bricht die aktuelle Schleife ab; Exit verlässt eine Function/Procedure
      end;
    end;
  end;
end;

Delphi-Quellcode:

(* Mein Senf; musst du dir nicht geben... *)

function IsPrime2( X: Integer ): Boolean;
var
  D: Integer;
begin
  {
    Die Wahrscheinlichkeit, dass bei einer Divison mit einem kleinen Divisor der Rest 0 ist, ist größer
    als bei einem großen Divisor - folglich lassen wir denn Divisor von 2 bis (x-1) steigen und nicht umgekehrt
    @Forum - Kann einer diesen Gedankenvorgang bestätigen, bin mir iwie gar nicht mehr so sicher =|
    (7 Dosen Energydrinks.. Konzentration lässt nach xD)
  }
  Result := False;
  if X > 2 then
  begin
    D := 2;
    repeat
      if X mod D = 0 then
        Exit;     // Brich die ganze Funktion ab (Rückgabewert ist False -> Siehe erste Zeile)
      inc( D );   // inc macht folgendes --> "D := D + 1" (ist eine Procedure, die eine Variable entgegen nimmt)
    until D = X;
    Result := True;
  end;
end;

MfG

[Sir Rufo]

Aus Performancegründen kann man die Prüfung auf diesen Bereich einschränken

Code:

1 < n <= X div 2

denn

Code:

für {X div 2 < n < X} gilt X mod n <> 0

[nachti1505]

Delphi-Quellcode:

function isPrime(a: integer): Boolean;
begin
  result := isPrimeRek(a, 2);
end;

function isPrimeRek(a, Teiler: integer): Boolean;
begin
  if (a mod Teiler = 0) then result := false
  else if (Teiler < Round(Sqrt(a)) + 1) then result := isPrimeRek(a, Teiler + 1)
  else result := true;
end;

[nachti1505]

Zitat:

Zitat von Sir Rufo (Beitrag 1055969)

Aus Performancegründen kann man die Prüfung auf diesen Bereich einschränken

Code:

1 < n <= X div 2

denn

Code:

für {X div 2 < n < X} gilt X mod n <> 0

Die Prüfung kann sgar auf

Code:

1 < n < Sqrt(X) + 1

beschränkt werden....

[DeddyH]

Zitat:

Zitat von Romiox (Beitrag 1055801)

Ich weiss, es gibt hier viele Threads zu dem Thema, aber erstens habe ich so meine Probleme anderer Leute Code zu lesen (Übungssache, nehm ich an^^)
und zweitens interessiert mich eigentlich mehr woran genau mein Code krankt, weniger der eigentlich Lösungsweg ;)

Bevor das hier noch zum Wettbewerb ausartet.

[Romiox]

Richtig, ich hab alles was ich wollte ;)

Vielen, vielen Dank trotzdem für alle eure Antworten, sind doch alle recht übersichtlich und nachvollziehbar,
und definitiv eine Bereicherung :)