Entwickler-Ecke :: Thema anzeigen - Primzahlen-Algorithmus

Startprogrammer - Do 12.12.02 21:16
Titel: Primzahlen-Algorithmus

Hallo,
Wir haben mal wieder eine neue aufgabe bekommen, und zwar sollen wir ein programm schreiben, dass testen kann, ob eine Zahl eine primzahl ist oder nicht, wir sollen jetzte einen algorithmus dazu schreiben, aber igendwie ist er mit meinem nicht zufrieden. Wir haben so einen virtuellen Klassenraum bei irgend so einem server, da stellen dann immer alle ihre sachen so online. Jetzt brauche ich im Laufe des Abénds noch einen neuen Algorithmus, aber ich bin mal wieder ratlos. Könnt ihr mir vielleicht helfen??? Schon mal Danke...

Startprogrammer - Do 12.12.02 21:21

Nochmal dazu, dass hier hat mein Lehrer geschrieben:

Zitat:

Optimierung des Primzahlenprogramms
Die meisten "Lösungen" sind eigentlich keine vollständigen Algorithmen. Einzig bei .... sind bislang komplette Strukturen erkennbar.
Als Tipp: Der Computer kann nicht automatisch Primzahlen erkennen. Das müssten wir ihm schon beibringen.
Es werden möglicherweise neue Funktionen gebraucht.
1. div, führt eine Ganzahldivision aus
2. mod berechnet den modulo-Wert, also den Rest bei einer Ganzahldivision (Wie früher in der Grundschule: 10 geteilt durch 3 ist 3 Rest 1. Die 1 ist dann der modulo-Wert.
Ist also der modulo-Wert 0, dann ist die Division ohne Rest. Damit ist die gewünschte Zahl teilbar.

Gestellt: 09.12.2002 09:09:13

Christian S. - Do 12.12.02 21:35

Du kannst folgendes verwenden, um mit beliebig hoher (aber nicht absolter!) Sicherheit festzustellen, ob eine Zahl eine Primzahl ist:

Ist n eine Primzahl, so gilt für alle ganzen Zahlen a, die nicht Vielfaches von n sind, folgendes:

(a^(n-1)) mod n = 1

Prüfst Du diese Bedingung für hinreichend viele Zahlen a, kannst Du sehr sicher sein, dass es sich um eine Primzahl handelt. a sollte irgendwie zwischen 2 und n-2 liegen, damit das ganze gut funktioniert. Ich würde so um die hundert Zahlen testen. Ich kenne hierfür leider nicht die Fehlerwahrscheinlichkeit (kenne ich nur für einen verbesserten, bei dem reichen 20, aber den habe ich nur als Java-Programm und keine Lust das umzuschreiben), aber sie dürfte lächerlich gering sein.

MfG,
Peter

Christian S. - Do 12.12.02 21:44

Oder die sichere Version (für kleine Zahlen):

(Zahl ist die zu testende Zahl)

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

VAR zahl, test : INTEGER;
    prim : Boolean;
begin
  prim:=true;
  test:=1;
  if (zahl mod 2) = 0 then prim:=false;
  while prim and (test < zahl div 2) do //bisher kein Teiler und Zahl kleiner als die Hälfte der zu testended Zahl
  begin
    test:=test+2;
    if zahl mod test = 0 then prim:=false;
  end;
  if prim then ShowMessage('Primzahl') else ShowMessage('teilbar');
end;

MfG,
Peter

P.S.: der Quelltext ist nicht getestet. Sollteste also nochmal drüber schauen.

Jack Falworth - Fr 13.12.02 18:10

was für ein Zufall. Das Thema hatten wir heut in der Schule.
Die oben genannte Vorschläge dürften funktionieren, aber sind nicht die schnellsten Algos.

Wenn du es optimieren willst kannst du z.B.
die Zahl durch 2 teilen. wenn das nicht funktioniert, werden alle geraden Zahlen durch die geteilt werden soll rausgeworfen.
...

MfG

Jack Falworth

Christian S. - Fr 13.12.02 18:14

Also, der erste Vorschlag ist für große Zahlen gedacht (also im Bereich von 10^6 oder so) und dort einer der schnellsten. Wer die verbesserte Variante haben möchte, soll im Internet mal unter "Miller-Rabin-Primzahltest" nachschauen.

Der zweite Vorschlag: da ich test:=test+2 verwende und mit einer ungeraden Zahl starte, wird auch bei mir nicht mit geraden Zahlen geprüft!

MfG,
Peter

Startprogrammer - Mo 16.12.02 16:31

Das ist jetzt mal der Code von einem aus meinem Kurs:

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

procedure TForm1.BtRechneClick(Sender: TObject);
   var   Zahl, Teiler  :Integer;
begin
   Zahl:=StrToInt(EdEingabe.Text);
   Teiler:=1;
     Repeat
      Teiler :=Teiler +1;
     Until Zahl mod Teiler =0;
If Teiler = Zahl
then LbAusgabe.Caption:='Pz'
else LbAusgabe.Caption:='Keine PZ'
end;
end.

Allerdings nur, um zu testen, ob eine Zahl prim ist.

Christian S. - Mo 16.12.02 17:20

1. Ich weiß zwar nicht mehr, warum man nur bis zur Wurzel testen muss, aber ich kann mich noch dran erinnern, das das stimmt.

2. Der Code ist nicht ernst gemeint, oder?

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!