Primzahlen ermitteln?

[DP-Maintenance]

Dieses Thema wurde von "Phoenix" von "Programmieren allgemein" nach "Sonstige Fragen zu Delphi" verschoben.
Hier gehts um Delphi...

[agm65]

hi wollte auchmal was posten.

Delphi-Quellcode:

uses
  math;

Function IsPrim(zahl : Integer): boolean;
var
i: integer;
begin
  result := true;
  If zahl = 1 then
  begin
    result := false;
    exit;
  end;
  For i := 2 to Trunc(sqrt(zahl))+1 do
  begin
    If ((zahl mod i) = 0) then
    begin
      result := false;
      exit;
    end;
  end;
end;


procedure TForm1.Button1Click(Sender: TObject);
var
i:integer;
begin


 for i := 0 to 1000 do
  begin
   if isprim(i)  then memo1.Lines.Add(inttostr(i));

 end;

end;

[3_of_8]

Ich hab grad mal just for fun wieder nen Primzahltester und -finder gebastelt. Eigentlich muss man überhaupt nicht mit dem Sieb des Erathostenes arbeiten, die Geschwindigkeit ist auch so hoch genug.

@agm65: Das hier dürfte schneller sein:

Delphi-Quellcode:

function IsPrimeNumber(AValue: Integer): Boolean;
var I: Integer;
begin
  Result:=False;
  if AValue<2 then exit;
  I:=2;
  while I*I<=AValue do
  begin
    if AValue mod I=0 then exit;
    inc(I);
  end;
  Result:=True;
end;

[MaBuSE]

Ich will auch mal was posten :-)

Eine einfach Lösung (ohne Optimierung!!!).
Aber als Beispiel für Jan13490 gut geeignet, da er schreibt Anfänger zu sein.

Mann muß natürlich nicht den ganzen Zahlenraum zwischen 1 und z durchlaufen,
aber diese Lösung ist einfach zu verstehen.

Delphi-Quellcode:

function isPrime(z: Integer):Boolean;
var
  i: Integer;
begin
  i := 2;
  // solange (z nicht durch i teilbar ist) und (i kleiner z ist) erhöhe i um 1
  while (z mod i > 0) and (i < z) do
  begin
    inc(i);
  end;
  // Bei z angekommen = Primzahl
  Result := (i = z); 
end;


procedure TForm1.Button1Click(Sender: TObject);
var
  i: Integer;
begin
  for i := StrToInt(Edit1.Text) to StrToInt(Edit2.Text) do
  begin
    // wenn i Prim, dann ab ins Memo
    if isPrime(i) then Memo1.Lines.Add(IntToStr(i));
  end;
end;

[Luckie]

Zitat:

Zitat von 3_of_8

die Geschwindigkeit ist auch so hoch genug.

@agm65: Das hier dürfte schneller sein:

Delphi-Quellcode:

function IsPrimeNumber(AValue: Integer): Boolean;
var I: Integer;
begin
  Result:=False;
  if AValue<2 then exit;
  I:=2;
  while I*I<=AValue do
  begin
    if AValue mod I=0 then exit;
    inc(I);
  end;
  Result:=True;
end;

Und sie kann och erhöht werden, in dem du nur bis zur Quadratwurzel testest.

[3_of_8]

Das tue ich. ;)

Siehs dir genau an.

[Nikolas]

Dann könntest du aber eine weitere Variable nehmen und da die Wurzel reinschreiben. Dann sparst du pro Schleife noch eine Multiplikation.

[3_of_8]

Nur ist die Wurzel eine Gleitkommaoperation, und ich glaube kaum, dass das schneller ist als die Multiplikationen.

[Nikolas]

Delphi-Quellcode:

function IsPrimeNumber(AValue: Integer): Boolean;
var I: Integer;
wurzel: integer;
begin
  Result:=False;
  Wurzel:=ceil(sqrt(AValue));
  if AValue<2 then exit;
  I:=2;
  while I<= Wurzeldo
  begin
    if AValue mod I=0 then exit;
    inc(I);
  end;
  Result:=True;
end;

[3_of_8]

Es ist trotzdem eine Gleitkommaoperation, und das ziehen einer Wurzel ist dabei nicht einmal eine besonders schnelle. Es ist eine denkbare Alternative, an die ich zuerst auch gedacht habe, aber dann nicht eingebaut habe. Aber auch die mit den Multiplikationen geht recht gut. ;)