Optimierung einer Primzahlfunktion

Kroni · Beiträge: 720 Win 98, Win ME, Win2k, Win XP D3 Pro

du du du.....
lass doch als Eingabe einer Zahl doch auch direkt nur INT64 zu....erspart auch nochmal zeit....
ansonsten bemerke ich mal, dass 1 laut definition auch eine Primzahl ist (1 ist durch sich selber und eins teilbar)...sowie die Null auch....also mach dann einfach eine da, wo zahl=2 or zahl=3 steht...einfach if zahl<4 then....
ansonsten ist das ja so grob mein Programm;-)
Was hast du denn für eine Taktfrequenz am Rechner??
Ansonsten würd ich, wenn du die Funktion aufrufst....auch nur direkt die Geraden Zahlen rausfiltern...also anstatt eine
FOR i:=start to endwert do

einfach ne while (i<=endwert) do
bla und adnn mit einer ungeraden zahl anfangen und dann i um zwei erhöhen...erspart auch nochmal ein paar millisekunden....

sourcehunter · Beiträge: 482 Win XP | Suse 10.1 Delphi 2005 Pers.

Brauchst du wirklich INT64? Also, wenn nich, dann nimm Integer, denn das ist viel schneller, weil ein 32-Bit-Prozessor einen 64-Bit-Integer emulieren muss. Oder reichen dir etwa 4 Mrd. nicht?

_________________
Linux und OpenSource rulez!

Kroni · Beiträge: 720 Win 98, Win ME, Win2k, Win XP D3 Pro

Zitat:

Ich brauche etwa zwischen 93 und 109 ms, irgendwas past da nicht :-D

mit welcher Funktion denn?
und wofür?*g*
genaue Angaben wären mal nich schlecht;-)

GTA-Place · Verfasst: Sa 27.11.04 00:50

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

function Prim (Zahl: Integer): Boolean;
var
  Teiler: Integer;
  Wurzel: Double;
begin
  Teiler := 3;
  Wurzel := sqrt(Zahl);
  while ((Teiler <= Wurzel) AND (result)) do
  begin
    if Zahl mod Teiler = 0 then
    begin
      Result := False;
      Break;
    end;
    inc(Teiler, 2);
  end;
end;

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:

procedure TMainForm.StartButClick(Sender: TObject);
var
  Start, Ende: Real;
  X, Von, Bis: Integer;
begin
  PrimS := TStringList.Create;
  PrimS.Add('2');
  PrimS.Add('3');

  Von := StrToInt(VonEdit.Text);
  Bis := StrToInt(BisEdit.Text);

  if Von < 4 then
    Von := 4;

  Start := GetTickCount;

  for X := Von to Bis do
  begin
    if odd(X) then
    begin
      if Prim(X) then
      begin
        PrimS.Add(IntToStr(X));
        Application.ProcessMessages;
        PrimLab.Caption := 'Aktuelle Primzahl: ' + IntToStr(X);
      end;
    end;
  end;

  Ende := GetTickCount;
  DauerLab.Caption := 'Diese Überprüfung hat ' + FloatToStr((Ende - Start) / 1000) + ' Sekunden gedauert.';

  PrimS.SaveToFile('test.txt');
  PrimS.Free;
end;

Kroni · Beiträge: 720 Win 98, Win ME, Win2k, Win XP D3 Pro

ich muss dich verbessern.....ich würde die abfrage ob das nun unter drei ist mit in der Funktion machen...denn so , wenn du meinetwegen zahlen von 5 bis 10 eingbist, erscheinen die Zahlen 1 2 3 immer....das ist ja nich sinn der Sache

GTA-Place · Verfasst: Sa 27.11.04 01:00

Habs jetzt so, aber nicht in der Funktion:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

  if Von < 4 then
  begin
    Von := 4;
    PrimS.Add('1');
    PrimS.Add('2');
    PrimS.Add('3');
  end;

Kroni · Beiträge: 720 Win 98, Win ME, Win2k, Win XP D3 Pro

immer noch nich ok.....wiel wenn du drei eingibst wird doch auch 1 2 3 angezeigt...mach doch in der Funktion ne Abfrage...

markieren

Delphi-Quelltext

1:
2:

if (zahl<4) then
exit;

Fertig....

GTA-Place · Verfasst: Sa 27.11.04 01:11

Jetzt wollen wir mal nicht so kleinlich sein ^^
Ob der jetzt 1, 2, oder 3 (letzte Chance vorbei... Ach ne, das war Kinderkanal, wir sind ja im Delphiforum... :roll:

) eingibt, ist doch eigentlich egal. Und wenn ich es in die Funktion schreibe, dann dauert es länger. Ich kanns ja trotzdm noch umschreiben:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

  if Von = 1 then  
  begin  
    Von := 4;  
    PrimS.Add('1');  
    PrimS.Add('2');  
    PrimS.Add('3'); 
  end;

  if Von = 2 then  
  begin  
    Von := 4;  
    PrimS.Add('2');  
    PrimS.Add('3'); 
  end;

  if Von = 3 then  
  begin  
    Von := 4;   
    PrimS.Add('3'); 
  end;

PS: Für 10 Mio Zahlen braucht das Prog. jetzt 82,984 Sekunden, bisschen schneller als gestern Abend ( :wink:

schon 10 Minuten Samstag :wink:

).

Kroni · Beiträge: 720 Win 98, Win ME, Win2k, Win XP D3 Pro

na ja....schreib die Function mal um...und dann mess mal die Zeit;-)

GTA-Place · Verfasst: Sa 27.11.04 01:20

Haha: Um 0,000000000001 Millisekunden langsamer ^^.

Kroni · Beiträge: 720 Win 98, Win ME, Win2k, Win XP D3 Pro

na ja....dann solltest du aba deineProzedur anders schreiben da oben....das geht noch kürzer....aba ich schreib die mal nun wieich das machen würd......
edit: ansonsten solltest du mal noch ne Eingabeabsicherung einbaeun, und nen Zähler....damit du weist, wie viele Primzahlen bzw ob Überhautp eine Primzahl ermittelet wurde.....

GTA-Place · Verfasst: Sa 27.11.04 01:37

Ich habs jetzt in die Funktion eingebaut.
Was meinst du mit Eingabesicherung, was soll gesichert sein?

Kroni · Beiträge: 720 Win 98, Win ME, Win2k, Win XP D3 Pro

na....dass dann zb mal anstatt eine Zahl ein Buchstabe ins Edit Feld eingegeben wird.....dass dann eine Fehlermeldung erscheint....das gehört ja normal zu jedem Programm.

GTA-Place · Verfasst: Sa 27.11.04 01:47

Jo, das kommt ja noch alles...

Kroni · Beiträge: 720 Win 98, Win ME, Win2k, Win XP D3 Pro

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

function Prim (Zahl: Integer): Boolean;
var
  Teiler: Integer;
  Wurzel: Double;
begin
  Teiler := 3;
  Wurzel := sqrt(Zahl); 
  result:=true;  //Hier solltest du auf jeden fall vorher result auf true setzten...sonst ist die Beleggung ja dem Zufall überlassene
  while ((Teiler <= Wurzel) AND (result)) do
  begin
    if Zahl mod Teiler = 0 then
    begin
      Result := False;
      Break;
    end;
    inc(Teiler, 2);
  end;
end;

GTA-Place · Verfasst: Sa 27.11.04 02:04

Eigentlich ist es net dem Zufall überlassen, denn Delphi setzt automatisch Result auf True;

Kroni · Beiträge: 720 Win 98, Win ME, Win2k, Win XP D3 Pro

echt? wusst ich nich......würd ich aba trotzdem machen.... ;-)

GTA-Place · Verfasst: Sa 27.11.04 02:16

Das machen wir dann alles morgen, aber jetzt geh ich erstmal in's Bett.
Gute Nacht!

Gausi · Verfasst: Sa 27.11.04 04:58

Kroni hat folgendes geschrieben:

ansonsten bemerke ich mal, dass 1 laut definition auch eine Primzahl ist (1 ist durch sich selber und eins teilbar)...sowie die Null auch....also mach dann einfach eine da, wo zahl=2 or zahl=3 steht...einfach if zahl<4 then....

Aus mathematischer Sicht ist das falsch. 1 ist keine Primzahl, sondern eine "Einheit". Also eine Zahl, die man mit einer anderen (ganzen) Zahl zu 1 multiplizieren kann. -1 ist auch eine Einheit. 1 ist speziell, weil es im "Ring" der ganzen Zahlen das "neutrale Element" der Multiplikation ist, d.h. 1*x=x für alle x.
0 ist ebenfalls keine Primzahl, sondern das neutrale Element der Addition, d.h. x+0=0 für alle x.
Und diese "besonderen Zahlen" sind aus der Definition der Primzahlen ausgenommen.

[genug kluggeschissen, viel Erfolg mit dem Programm]

_________________
We are, we were and will not be.

GTA-Place · Verfasst: Sa 27.11.04 09:16

Danke.
Jetzt ist die Frage: Machen wir ein gemeinsames Projekt, oder machst du das weiter, wofür du die Primzahlfunktion benötigt hast und ich mach mein eigenes Projekt?

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme