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 :thumb:

[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

[Sir Rufo]

Als erstes solltest du planen, dir eine eigene

Delphi-Quellcode:

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;

[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

[Mathematiker]

Hallo,

Zitat:

Zitat von Sir Rufo (Beitrag 1323121)

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

[Sir Rufo]

Zitat:

Zitat von Mathematiker (Beitrag 1323123)

Hallo,

Zitat:

Zitat von Sir Rufo (Beitrag 1323121)

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.

I know :stupid:

Ich wollte in dem Quelltext die Vorüberlegung

Zitat:

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

quasi 1:1 reinbringen.

Als Lerneffekt: Eigentlich programmiere ich so, wie man denkt/spricht/schreibt.

Die gerundete Quadratwurzel als Maximum und mit dem kleinesten Wert beginnen ist dann Performance-Optimierung.

Also nach dem Motto:

Zitat:

1. Make it work
2. Make it fast

;)

[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 :lol:
Danke nochmal

Zitat:

Zitat von frankyboy1974 (Beitrag 1323120)

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:

Zitat von BlackPegasus (Beitrag 1323125)

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

Delphi-Quellcode:

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

[Perlsau]

Sollte man nicht als erstes mal prüfen, ob die zu prüfende Zahl

• eine gerade Zahl ab 3 (durch 2 teilbar) ist, denn gerade Zahlen sind, abgesehen von der 2, keine Primzahlen;
• durch 3 teilbar ist, denn das erfährt man durch die Ermittlung der Quersumme bis zum Gehtnichtmehr;
• ... und was da noch für schöne mathematische Tricks existieren, die schneller durch sind als das sture Brut-Force-Teilen durch alle kleineren Zahlen?

Obwohl ich kein Mathematiker bin und daher auch nicht das Primzahlsieb des Eratosthenes kenne, werd' ich mich mal drüber hermachen. Schaun mer mal, ob ich das begreife:

Delphi-Quellcode:

Type
  TPrimeTest = Record
    Zahl : Integer;
    Mark : Byte;
  End;

Man macht sich also ein Record-Array vom Typ TPrimeTest, befüllt die Integerwerte mit dem zu testenden Zahlenbereich und setzt die Byte-Werte auf 0 als Marker für ungetestet:
Dann fängt man an zu sieben, indem man das Array durchiteriert, wobei man gleich mal die ungeraden Vielfachen der aktuellen Zahl, falls vorhanden, mit 1 als Marker für keine Primzahl und natürlich für getestet markiert. Gerade Zahlen, die größer als 3 sind, muß man erst gar nicht aufnehmen, da die sowieso keine Primzahlen sind, weil sie ja alle durch 2 ohne Rest teilbar sind und ihre Vielfachen ebenfalls. Bei 3 blättert man also im Array weiter, bis man auf die 9 stößt, und setzt dessen Bytewert auf 1 (keine Primzahl). Ebenso verfährt man bei der 15 (3x5), der 21 (3x7), 27 (3x9), 33 (3x11) usw. bis zur Maximalzahl, also der Suchgrenze bzw. der Obergrenze des zu durchsuchenden Zahlenbereichs. Vielfache von Geraden kann man sich hier ebenfalls sparen, denn die sind auf jeden Fall auch immer gerade Zahlen und daher keine Primzahlen. Ebenso kann man sich Multiplikatoren sparen, die kleiner sind als die jeweilige Zahl, denn die wurden ebenfalls bereits markiert. Beim zweiten Durchgang hat man dann schonmal viele Zahlen, die Vielfache von kleineren Zahlen sind, als Nicht-Primzahl markiert und muß die nicht mehr prüfen, sondern nur noch die, die den Marker 0 für ungetestet führen. Ebenso verfährt man bei der 5, wo man mit 5x5 beginnt, bei der 7, der 11 (die 9 wurde ja bereits getestet) usw.

Der Satz "Nachdem eine Primzahl gefunden wurde, werden alle Vielfachen dieser Primzahl als zusammengesetzt markiert." leuchtet mir jetzt langsam ein, denn alle Nicht-Primzahlen, die man im weiteren Verlauf des Hochzählens antrifft, wurden ja bereits als Vielfaches einer kleineren Zahl erkannt und markiert. Man kann daher etliches an Rechenzeit sparen, wenn man etwas intelligenteres macht als brute force.

Ich hab's jetzt nicht getestet, dafür bin ich heute abend schon zu faul und zu müde (wach seit 4:30 Uhr), also lustlos, kein Bock oder was auch immer. Aber etwas ist mir im Wikipedia-Artikel trotzdem noch aufgefallen, dafür reicht's gerade eben noch:

Das Verfahren beginnt also damit, die Vielfachen 4, 6, 8,… der kleinsten Primzahl 2 durchzustreichen. Die nächste unmarkierte Zahl ist die nächstgrößere Primzahl, die 3. Anschließend werden deren Vielfache 9, 12, 15,… durchgestrichen, und so weiter.

Wenn man die geraden Zahlen erst gar nicht ins Array aufnimmt, muß man sie weder prüfen noch "streichen". Das heißt, man muß auch die jeweiligen Vielfachen jener verbliebenen Ungeraden Zahlen, die aus einer Multiplikation mit einer geraden Zahl hervorgehen, nicht prüfen, denn dieses Resultat ist immer eine gerade Zahl und daher niemals eine Primzahl. Zudem kann man auch alle Zahlen, die am Ende eine 5 aufweisen, übergehen, denn die sind alle durch 5 teilbar.

Hat das der Eratosthenes damals vor 2.285 Jahren nicht bemerkt oder ist der Wikipedia-Artikel diesbezüglich fehlerhaft?