Optimierung einer Primzahlfunktion

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

weist du denn, wie man ne StringList macht??
du musst dann ja eine createn usw.....grob weiß ichs, aba habs noch nie ausprobiert.....
dann kannst du nachdem du alle Ermittelt hsat quasi erst dann alle Primzahlen ausgeben lassen oder wie auch immer...oder in einer Textdatei speichern....wäre von Vorteil oda?

GTA-Place · Verfasst: Fr 26.11.04 22:01

Genau. Jo, ich weiß wie es geht.

markieren

Delphi-Quelltext

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

var
  Prim: TStringList;
begin
  Prim := TStringList.Create;
  Prim.Add(Primzahl);
  Prim.SaveToFile('Pfad');
  Prim.Free;
end;

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

aber du gehst doch dann auch von meinetwegen um die Primzahlen zwischen 1 und 100000 herauszufinden alle Zahlen durch,....und guckst dann ob das Primzahlen sind, wobei du ja eigentlich von 9 aus gesehen jede zweite Zahl Prüfen musst oder hab ich mich da grad vertan?

GTA-Place · Verfasst: Fr 26.11.04 22:10

Fast. Wie ich bemerkt habe, reicht es nicht nur jede 2. Zahl zu prüfen.

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

doch doch....wenn du von neun ausgehst....dann reicht es doch vollkommen...oda hast du mal eine gerade zahl außer zwei gesehen, die Primzahl ist?

GTA-Place · Verfasst: Fr 26.11.04 22:17

Ich weiß warum es net ging bei mir: Zaehler := 2
Wenns mit 3 beginnt stimmts: 3, 5, 7, 9, 11, 13,...

EDIT: So wird mir aber immer 4*x angezeigt als Prim.

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

na ja, vertrau mir mal, einmal ein einziges mal^^ und du wirst sehen, du braucht nur die Hälfte der Zeit, sitmmts? *gggg*

GTA-Place · Verfasst: Fr 26.11.04 22:20

Ne, wird auch 4, 8, 16, 20,... als Prim angezeigt.

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

stell nochma den kompletten code online bidde.....dann kann ich dir sagen worans liegt*hoff*
das kann doch nich sein....du musst doch nur die ungeraden zahlen prüfen....wie kommen dann überhaupt die geraden zahlen in die Überprüfung?????

GTA-Place · Verfasst: Fr 26.11.04 22:24

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:

function Prim (Zahl: Real): Boolean;
var
  Zaehler: Integer;
  Wurzel: Double;
  Z64: Int64;
begin
  if (Zahl = 2) OR (Zahl = 3) then
  begin
    Result := True;
    Exit;
  end;
  Wurzel := sqrt(Zahl);
  Zaehler := 3;
  Z64 := Trunc(Zahl);
  repeat
    if (Z64 mod Zaehler) = 0 then
    begin
      Result := False;
      Exit;
    end;
    Inc(Zaehler, 2);
  until Zaehler > Wurzel;
  Result := True;
end;

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

ja, das ist ja die funktion...aba mit welchem code rufst du die Prüfungsfunktion auf?????
in dem code, mit dem du die Zahl, die du prüfst erhöst, darin muss der Fehler sein!

GTA-Place · Verfasst: Fr 26.11.04 22:30

markieren

Delphi-Quelltext

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

  for X := StrToInt(VonEdit.Text) to StrToInt(BisEdit.Text) do
  begin
    if Prim(X) then
      PrimS.Add(IntToStr(X));
      Application.ProcessMessages;
      PrimLab.Caption := 'Aktuelle Primzahl: ' + IntToStr(X);
  end;

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:
19:
20:
21:
22:
23:
24:

function Prim (Zahl: Real): Boolean;
var
  Zaehler: Integer;
  Wurzel: Double;
  Z64: Int64;
begin
  if (Zahl = 2) OR (Zahl = 3) then
  begin
    Result := True;
    Exit;
  end;
  Wurzel := sqrt(Zahl);
  Zaehler := 2;
  Z64 := Trunc(Zahl);
  repeat
    if (Z64 mod Zaehler) = 0 then
    begin
      Result := False;
      Exit;
    end;
    Inc(Zaehler);//Du musst doch jede Zahl durchgehen, ob sie Teiler ist!!!!! und dann bitte auch von zwei an....dann muss das funzen
  until Zaehler > Wurzel;
  Result := True;
end;

GTA-Place · Verfasst: Fr 26.11.04 22:36

Hatte ich die ganze Zeit, bis der eine, den neuen Code gepostet hat.

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

ok....hab grad mal über was nachgedacht:

1. du kontrollierst nur zahlen, wenn sie ungerade sind und gleich zwei.....
2. wenn die zahl also gerade ist, dann ist die Zahl keine Primzahl...bis auf die Zwei
3. Wenn du also allgemein die Ungeraden Zahlen kontrollierst, fängst du bei der Drei an....und dann musst du nur durch ungerade Teiler teilen......
Das wärs....
das wäre dann die schnellste Version die mir einfällt....
Klingt logsich oda?

GTA-Place · Verfasst: Fr 26.11.04 22:51

Und wie siehts jetzt im Sourcecode aus?

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:
19:
20:
21:
22:

function prim(zahl:integer):boolean;
var teiler:integer;
    wurzel:extended;
begin
result:=true;
teiler:=3;
if ((zahl mod 2)=0) then  //Zahl gerade
 result:=false
else
  begin
  if (zahl=2) then
    exit
  else
    begin
    while ((teiler<=wurzel) and result) do
      begin
      if ((zahl mod teiler)=0) then
        result:=false;
      inc(zahl,2);
      end;
    end;
end;

versuchs ma...habs grad nich getestet

GTA-Place · Verfasst: Fr 26.11.04 23:32

Umgeschrieben siehts so aus:

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:

function Prim (Zahl: Real): Boolean;
var
  Zaehler: Integer;
  Wurzel: Double;
  Z64: Int64;
begin
  Z64 := Trunc(Zahl);
  if (Zahl = 2) OR (Zahl = 3) then
    Exit;
  if (Z64 mod 2 = 0) OR (Zahl = 1) then
  begin
    Result := False;
    Exit;
  end;
  Wurzel := sqrt(Zahl);
  Zaehler := 3;
  repeat
    if (Z64 mod Zaehler) = 0 then
    begin
      Result := False;
      Exit;
    end;
    Inc(Zaehler, 2);
  until Zaehler >= Wurzel;
  Result := True;
end;

1-100.000 dauert 9,906 Sekunden.

Wenn man das ganze mit ASM macht dauert es 9,968.
Unsere Fumktion ist besser ^^

GTA-Place · Verfasst: Fr 26.11.04 23:55

Wollt ihr wissen, wieviel jetzt noch für 1-100.000 benötigt wird? 1,188 Sekunden.

Benutzername · Beiträge: 210 Win XP Pro Delphi 7 PE, D2005 Prof. SSL

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

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme