Primzahlen-Programm

[BlackPegasus]

Hallo,
Ich will mit der For-Schleife ein Programm programmieren, das erkennt, ob es sich um eine Primzahl oder keine handelt.
Ich will bzw. muss auf die IsPrime() Funktion verzichten und es irgendwie mit der For-Schleife hinbekommen.
Meine Idee:

Code:

procedure TForm1.Button1Click(Sender: TObject);
begin
zahl:=Strtoint(Edit1.Text);
l:=trunc(sqrt(zahl));

for i:=2 to l do begin
erg:=zahl mod i;
if
erg=0
then begin
Label2.Caption:='Das ist keine Primzahl';
end
else
Label2.Caption:='Das ist eine Primzahl';
end;
end;

end.

Leider funktioniert es nicht bei allen Zahlen ...
Bin noch Neuling auf dem Gebiet,
hab auch lange genug recherchiert und nichts passendes gefunden.
Hoffe ihr könnt mir helfen

[frankyboy1974]

hallo,

Delphi-Quellcode:

zahl:=Strtoint(Edit1.Text);
l:=trunc(sqrt(zahl));
isPrim:=true;//boolean
for i:=2 to l do begin
  erg:=zahl mod i;
  if erg=0
  then begin
    Label2.Caption:='Das ist keine Primzahl';
    isPrim:=false;
    break;
  end;
end;
if isPrim then Label2.Caption:='Das ist eine Primzahl';

mfg

[p80286]

Das sollte die richtigen Ergebnisse liefern:

Delphi-Quellcode:

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  i : integer;

function IstPrimzahl(zahl:integer):boolean;
var
  i : integer;
  max : integer;
begin
  result:=true;
  max:=trunc(sqrt(zahl));
  for i:=2 to max do
    if zahl mod i = 0 then result:=false;
end;


begin
  try
    { TODO -oUser -cConsole Main : Code hier einfügen }
    for i:=1 to 128 do begin
      if IstPrimzahl(i) then  writeln(inttostr(i)+' ist eine Primzahl')
      else writeln(inttostr(i)+' ist keine Primzahl');
    end;
    readln;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.

Gruß
K-H

[BlackPegasus]

Danke an alle!!!
Die meisten Antworten sind schon zu fortgeschritten für mich

aber das hier, scheint mir am unkompliziertesten.
nur eine Frage, könnt ihr mir die Funktion

Code:

isPrim:=true;//boolean

in diesem Kontext erklären?
Ich versteh irgendwie nicht was es mir genau da bringt
Danke nochmal

Zitat von frankyboy1974:

hallo,

Delphi-Quellcode:

zahl:=Strtoint(Edit1.Text);
l:=trunc(sqrt(zahl));
isPrim:=true;//boolean
for i:=2 to l do begin
  erg:=zahl mod i;
  if erg=0
  then begin
    Label2.Caption:='Das ist keine Primzahl';
    isPrim:=false;
    break;
  end;
end;
if isPrim then Label2.Caption:='Das ist eine Primzahl';

mfg

[Mathematiker]

Hallo,

Zitat von BlackPegasus:

nur eine Frage, könnt ihr mir die Funktion

Code:

isPrim:=true;//boolean

in diesem Kontext erklären?

In der Variablen isPrim wird gespeichert, ob die zu untersuchende Zahl einen echten Primteiler hat.
Findest du einen Teiler, so wird isPrime auf false gesetzt.
Im abschließenden Test wird nur dann "Das ist eine Primzahl" ausgegeben, wenn isPrime nicht(!) falsch ist. Damit dies garantiert wird, muss vor der Schleife isPrime auf true gesetzt werden.

Beste Grüße
Mathematiker

[frankyboy1974]

hallo,

isPrim ist in diesem Zusammenhang keine Funktion sondern eine Variabel und zwar vom Typ 'boolean'. Da in deinem Quellcode auch kein Var Bereich angegeben war, bin ich davon ausgegangen, dass die Variablen global definiert sind.

Am Anfang wird die Variable isPrim auf true gesetzt, sofen du einen Teiler findest setzt du den Wert auf false. Sofern am Ende die Variable immer noch auf true steht, hast du also keinen Teiler gefunden und somit ist es eine Primzahl.


mfg

[BlackPegasus]

Ok, vielen Dank!

[Perlsau]

Zitat von BlackPegasus:

Ok, vielen Dank!

Jetzt haben wir dich voll erschlagen, nicht wahr?

[Sir Rufo]

Als erstes solltest du planen, dir eine eigene IsPrime Funktion zu schreiben.

Delphi-Quellcode:

function IsPrime( Value : Int64 ) : Boolean;
begin
  Result := ( Value mod 2 = 0 ); // Ein Fake
end;

procedure TForm1.Button1Click(Sender: TObject);
const
  CBoolStr: array[Boolean] of string = ['keine', 'eine'];
begin
  Label2.Caption := Format( 'Das ist %s Primzahl', [CBoolStr[ IsPrime( Strtoint( Edit1.Text ) ) ] );
end;

Dann überlegen wir uns mal, wann ist eine Zahl eine Primzahl?

Wenn diese nur durch sich selbst oder 1 ohne Rest teilbar ist.

Gut, dann machen wir das doch mal

Delphi-Quellcode:

function IsPrime( Value : Int64 ) : Boolean;
var
  lIdx: Int64;
begin
  // Wir berechnen Primzahlen nur, wenn die größer als 0 sind
  if Value <= 0 then
    raise EArgumentException.CreateFmt( 'Value %d must be greater than zero!', [Value] );

  // Wir prüfen nicht den Wert selber und auch nicht die 1
  for lIdx := Value - 1 downto 2 do
  begin
    // Ist der Wert ohne Rest teilbar?
    if Value mod lIdx = 0 then
    begin // dann ist es keine Primzahl
      Result := False; // also ist es False
      Exit; // und wir können Feierabend machen
    end;
  end;
  // Wenn wir bis hier kommen, dann ist es eine Primzahl
  Result := True;
end;

[Mathematiker]

Hallo,

Zitat von Sir Rufo:

Delphi-Quellcode:

function IsPrime( Value : Int64 ) : Boolean;
...
  // Wir prüfen nicht der Wert selber und auch nicht die 1
  for lIdx := Value - 1 downto 2 do
...

Sorry. Das sollte man auf keinen Fall tun.
Erstens sind kleine Teiler p häufiger Primteiler (Wahrscheinlichkeit 1/p) als große, so dass man von 2 bis zum Endwert prüft und abbricht, wenn die Zahl keine Primzahl ist.
Und zweitens ist der letzte zu testende Wert die (gerundete) Quadratwurzel von value. Alle größeren Teiler sind Komplementteiler von kleineren und deshalb nicht mehr zu überprüfen.

@BlackPegasus: Die Frage ist, in welcher Größenordnung sind die zu testenden Zahlen. Das Primzahlsieb des Eratosthenes (Googeln!) ist immer eine Überlegung wert, da es extrem schnell ist.

Beste Grüße
Mathematiker