Primzahlen ermitteln?

[Jan13490]

Hi Leute,
wollte mal ein Programm basteln, was Primzahlen finden kann.(Bin delphi anfänger)
Ich wollte es so machen, dass ich eine Kleinste und eine größte Zahl variabel eingeben kann und der PC sucht mir dann die Primzahlen zwischen den beiden Zahlen heraus.
Nur leider weiß ich überhaupt nicht wie ich das machen könnte.
Hat einer vllt sowas schon mal programmiert? Hat einer den quelltext?

Gruß jan

[fLaSh11]

Such mal nach dem Sieb des Erathostenes (evtl. noch ein "h" :mrgreen: )

[sakura]

Zitat:

Zitat von Jan13490

wollte mal ein Programm basteln, was Primzahlen finden kann.(Bin delphi anfänger)...Hat einer den quelltext?

Was bringt Dir der fertige Quelltext, welchen Du über die Suche im Forum als auch bei Google oft genug suchst?

Ansonsten sage uns doch mal wie weit Du bist und wo es genau Probleme gibt.

...:cat:...

P.S.: Hört sich sehr nach Hausaufgaben an...

[Gremlin]

Hi,

mit Quelltext wird es schwierig werden.
Lieber selbst (am Anfang) schlecht gemacht als gut kopiert.

Für den Anfang benötigst du zwei Eingabefelder für die Bereichseingabe.
Dann könntest du ein Schleifenkonstrukt verwenden, um alle Zahlen des Bereichs zu überprüfen.
Sollte im Prüfvorgang eine Primzahl entdeckt worden sein, dann gib diese aus.

Grüsse G.

PS: Hier sind Informationen über Primzahlen

[Jan13490]

hier ist mein quelltext:

Delphi-Quellcode:

unit UNT_Primzahl;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TFRM_Primzahlenfinder = class(TForm)
    BTN_Rechnen: TButton;
    EDT_zeitausgabe: TEdit;
    LBL_zeitausgabe: TLabel;
    LBX_Prim: TListBox;
    LBL_Primzahlen: TLabel;
    LBL_Primzahl: TLabel;
    BTN_Close: TButton;
    EDT_UG: TEdit;
    EDT_OG: TEdit;
    LBL_UG: TLabel;
    LBL_OG: TLabel;
    procedure BTN_CloseClick(Sender: TObject);
    procedure BTN_RechnenClick(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  FRM_Primzahlenfinder: TFRM_Primzahlenfinder;

implementation

{$R *.dfm}

var zeit, uG, oG : longint;
    h,m,s,ms : word;
    sieb: array [2..1000000] of boolean;

//function teileranzahl(zahl:longint):integer;
//var teiler, partnerteiler : longint;
//    anzahl                : integer;
//begin
//  anzahl := 2;
//  teiler := 2 ;partnerteiler := zahl div teiler;
//  while teiler < partnerteiler do
//    begin
//      if zahl mod teiler = 0 then
//        anzahl := anzahl+2;
//      inc(teiler); partnerteiler := zahl div teiler;
//    end;
//  if teiler*teiler = zahl then inc(anzahl);
//  teileranzahl := anzahl;
//end;

//function prim_1(zahl:longint):boolean;
//begin
//  prim_1 := teileranzahl(zahl) = 2;
//end;

procedure TFRM_Primzahlenfinder.BTN_CloseClick(Sender: TObject);
begin
close;
end;

procedure eratosthenes(obG:longint);
var index: longint;

procedure streiche_vielfache(i : longint);  {lokal deklarierte procedure, die nur                 
                                                                          in der procedure eratosthenes
                                                                          verwendet werden kann }
var k : longint;
begin
  k := i+i;
  while k <= oG do
    begin
      sieb[k] := false;
      k := k+i;
    end;
end;

begin     {eratosthenes}
  for index := 2 to oG do sieb[index] := true;    {initialisieren}
  index := 2;
  while index*index <= oG do
    begin
      if sieb[index] = true then streiche_vielfache(index);
      inc(index);
    end;
end;       {eratosthenes}



procedure TFRM_Primzahlenfinder.BTN_RechnenClick(Sender: TObject);
var //zahl, teiler : integer;
    uG, oG, index : longint;
begin
decodetime(time,h,m,s,ms);
zeit := 1000*(3600*h+60*m+s)+ms;
LBX_Prim.Items.clear;
uG := strtoint(EDT_UG.Text);
oG := strtoint(EDT_OG.Text);

eratosthenes(oG);
for index := uG to oG do
if sieb[index] = true then ;
LBX_Prim.Items.add(inttostr(index));

decodetime(time,h,m,s,ms);
zeit := 1000*(3600*h+60*m+s)+ms-zeit;
EDT_zeitausgabe.text := inttostr(zeit);
end;

end.

[edit=Matze]Code in Delphi-Tags eingefasst. Das nächste Mal bitte selbst machen. Mfg, Matze[/edit]

[gekkorist]

Delphi-Quellcode:

Var
prime, x: Integer;
begin

prime := StrToInt(Edit1.text);
x := 1;
//größer als 1 = beginnen
If prime > 1 then
begin
Repeat
x := x + 1;
//gucken ob x einen rest von 0 hat und durch eine zahl die größer als "eingabe" teilbar is"
Until (x > prime div x) or (prime Mod x = 0) ;

if x> prime div x
then
begin
Label1.Caption:=Edit1.text+ ': Ja, Primzahl.' ;
label1.Color :=clgreen;
end

else
begin
Label1.Caption:=Edit1.text +': Nein, keine Primzahl.';
label1.Color :=clred;
end;
end
 // 1 und 0
else
begin
if prime = 1 then
begin
Label1.Caption:='1: Nein, keine Primzahl.' ;
label1.Color :=clred;
end;
if prime=0 then
begin
Label1.Caption:='0 weiss ich nicht :).';
label1.Color :=clred;
end;
end;

// ohh is nur wenn eine Zahl eingegebn ist, aber das umzuändern is sicherlich net schwer!

[leddl]

Könntet ihr 2 eure Codes bitte in Delphi-Tags einschließen? :zwinker:

[Nikolas]

sieht doch ganz gut aus. Du musst beim Sieb aber nur bis zur Hälfte der Zahlen gehen, weil sonst die vielfach über deiner oberen Grenze liegen. Auch ist das hardgecodete Array nicht schön. Schau dir doch mal dynamische Array an.

[Jan13490]

Nur leider blick ich fast selbst durch mein programm nicht mehr durch.
Irgendwo muss da ein Fehler sein, nur ich find den nicht.

[Gremlin]

Wie äussert sich der Fehler denn?

[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. ;)

[Nikolas]

Du musst für fast jede untersuchte Zahl eine Muliplikation machen, und ich nur eine Wurzel ziehen. Bei größeren Zahlen könnte sich das bemerkbar machen.

[3_of_8]

Ja, bei größeren Zahlen mit Sicherheit.

Übrigens: Ich habe hier gerade ein Sieb des Erathostenes mithilfe eines Bitvektors realisiert und innerhalb von 74 Sekunden alle Zahlen von 0 bis 2^28 überprüft. Sollte Interesse bestehen, kann ich den Code mal posten.

[ThE_-_BliZZarD]

*Interesse anmeld*
Poste mal bitte den Code :-D

[3_of_8]

Bittesehr, sogar ein kleines bisschen schneller als die verbesserte Version in der CL, die ich erst nachträglich gefunden habe. Im übrigen, die reine Berechnung von 2^28 Werten geht in 20 Sekunden, die restlichen 54 gingen für die Ausgabe in die Dateien (56 MB) drauf.

[alzaimar]

Es geht auch in ca. 1.5 Sekunden, hier

[3_of_8]

Aber nur mit einer Art hartkodierten Primzahltabelle bis ~2^15, wenn ich das richtig sehe.

[alzaimar]

Auch Ohne wär es schneller, denn es verwendet eine Optimierung von Atkin. Das Erzeugen aller 16-bit Primzahlen dauert doch auch nur ein paar 100ms.