| Autor |
Beitrag |
Startprogrammer
Hält's aus hier
Beiträge: 9
|
Verfasst: Do 12.12.02 22:16
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 
Hält's aus hier
Beiträge: 9
|
Verfasst: Do 12.12.02 22: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.
  
Beiträge: 20451
Erhaltene Danke: 2264
Win 10
C# (VS 2019)
|
Verfasst: Do 12.12.02 22: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
_________________ Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
|
|
Christian S.
Beiträge: 20451
Erhaltene Danke: 2264
Win 10
C# (VS 2019)
|
Verfasst: Do 12.12.02 22: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. _________________ Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
|
|
Jack Falworth
Beiträge: 222
Win XP Pro, Slackware 10.0
D5 Enterprise, C++, ABAP
|
Verfasst: Fr 13.12.02 19: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.
Beiträge: 20451
Erhaltene Danke: 2264
Win 10
C# (VS 2019)
|
Verfasst: Fr 13.12.02 19: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
_________________ Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
|
|
CenBells
Beiträge: 1547
Win 7
Delphi XE5 Pro
|
Verfasst: Mo 16.12.02 01:05
Was vor allem noch wichtig ist, man brauch nicht bis zahl div 2 probieren.
es reicht, das man nur bis zur wurzel testet.
Gruß
Ken
|
|
Startprogrammer
Hält's aus hier
Beiträge: 9
|
Verfasst: Mo 16.12.02 17: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.
Beiträge: 20451
Erhaltene Danke: 2264
Win 10
C# (VS 2019)
|
Verfasst: Mo 16.12.02 18: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?
_________________ Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
|
|
Startprogrammer
Hält's aus hier
Beiträge: 9
|
Verfasst: Mo 16.12.02 22:52
Es ist kein Scherz, so ist der Code.
|
|
