 |
 |
 |
 |
 |
 |
Startseite » Forum » Zusammengesetzte Zahlen, natürl. Teiler<100
Zusammengesetzte Zahlen, natürl. Teiler<100
Schüler Gymnasium, 12. Klassenstufe
Tags: natürliche Teiler, Primzahl, Probedivision, zusammengesetzte Zahlen
 
|
  |
|---|
|
Als ich mir den Quellcode eines Programms zur Überprüfung auf Primzahlen durchgelesen habe, fiel mir auf, dass bei der Probedivision der zu untersuchenden Zahl nur die natürlichen Teiler von 2 bis überprüft werden. Aber selbst als ich sehr große Zahlen eingegeben habe, wurden sie richtig als zusammengesetzte Zahl oder Primzahl erkannt. Meine Vermutung lautet, dass irgendwann eine so große zusammengesetzte Zahl auftritt, dass sie keinen natürlichen Teiler hat und deshalb vom Programm als Primzahl erkannt werden müsste, obwohl es in Wirklichkeit einen natürlichen Teiler gibt, der ist. Nach langem Herumprobieren habe ich diese Zahl aber nicht finden können, die eine falsche Primzahl sein soll. Meine Frage lautet deshalb: Haben alle positiven zusammengesetzten Zahlen einen natürlichen Teiler, der kleiner ist? Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
| Hierzu passend bei OnlineMathe: Online-Übungen (Übungsaufgaben) bei unterricht.de: |
|
 |
|
Hallo, "Haben alle positiven zusammengesetzten Zahlen einen natürlichen Teiler, der kleiner ist?" Wenn man die 1 als Teiler unberücksichtigt läßt: Nein! Nimm eine beliebige Primzahl . Für findest Du keinen Teiler kleiner als und trotzdem ist keine Primzahl! Was das Programm angeht, kommt es darauf an, was es und vor allem wie macht. Ist der Quellcode öffentlich zugänglich, dann würde mich der schon mal interessieren... |
 |
|
Danke, stimmt tatsächlich :-) Also bleibt einem bei der Probedivision weiterhin nichts übrig, als alle möglichen natürlichen Teiler einer zu untersuchenden Zahl zu überprüfen, bis der natürliche Teiler gleich die zu untersuchende Zahl ist, was bei größeren Zahlen viel Rechenaufwand bedeutet. Der Quellcode ist öffentlich zugänglich. Eine Schülerin hat ihn auf unserem Schulserver hochgeladen und da hat jeder aus dem Jahrgang Zugriff drauf. Es ist in Delphi geschrieben. unit Unit1; $mode objfpc}{$H+} interface uses Classes, SysUtils, FileUtil, LResources, Forms, Controls, Graphics, Dialogs, StdCtrls; type TForm1 } TForm1 = class(TForm) Button1: TButton; Edit1: TEdit; Label1: TLabel; Label2: TLabel; Label3: TLabel; Label4: TLabel; procedure Button1Click(Sender: TObject); private private declarations } public public declarations } end; var Form1: TForm1; rest: Integer; PZflag: boolean; implementation TForm1 } procedure TForm1.Button1Click(Sender: TObject); begin label3.Caption edit1.Text; StrToInt(edit1.text); PZflag true; While and (PZflag = true) do begin if then rest if (rest=0) then PZflag false else end; if PZflag = true then label4.caption 'ist eine Primzahl' else label4.caption 'ist keine Primzahl' end; initialization $I unit1.lrs} end. |
|
|
|
Hallo, "Also bleibt einem bei der Probedivision weiterhin nichts übrig, als alle möglichen natürlichen Teiler einer zu untersuchenden Zahl zu überprüfen, bis der natürliche Teiler gleich die zu untersuchende Zahl ist" Leider nicht korrekt! Für jeden Teiler einer natürlichen Zahl mit gilt: ist eine natürliche Zahl und . Demzufolge genügt es alle Teiler bis einschließlich zu überprüfen. Gibt es bis dahin keinen Teiler, gibt es auch später keinen Teiler mehr... Außerdem muß man nicht alle natürlichen Zahlen testen, denn es genügt die Teiler zu finden, die eine Primzahl sind, man muß also nur alle Primzahlen testen. Da das allerdings erfordert, alle Primzahlen bis zu kennen, ist das nicht so praktikabel. Aber man weiß, dass alle Primzahlen größer als 3 immer darstellbar sind als . man testet nur mit diesen Zahlen. Ein sehr simpel zu programmierender Algorithmus würde also zunächst die Wurzel der Zahl ermitteln (abgerundet auf eine natürliche Zahl) und dann die 2 und die 3 für einen Test hernehmen um anschließend mit der 5 beginnend in einem Loop, der bei der Wurzel endet, die Testzahl abwechselnd um 2 und 4 erhöhen. Dieser Algorithmus ist nicht effektiv aber simpel zu programmieren... PS: Ohne Delphi im Detail zu kennen, funktioniert der Algorithmus sicher nur für Zahlen . Das liegt daran, dass ist. Ich hatte auf Hinweise eines iterativen Algorithmus gehofft, aber die kann ich hier wahrlich nicht finden. Allerdings sehe ich auch keine Prüfung der zu testenden Zahl, ob diese größer als ist. Vielleicht steckt das in den benutzten Klassen, weiß ich nicht, im Algorithmus ist dieser Test jedenfalls nicht enthalten. Du hast geschrieben, dass Du große Zahlen versucht hast, probiere doch mal aus, das ist . |
|
|
|
Also ich habe das Ganze mal durchprobiert. . Wurzel(23)=4.7958... Das wird dann aberundet auf . für alle Teiler . . . . sollen natürliche Zahlen rauskommen, aber die obigen ergeben keine natürlichen Zahlen. Ich nehme an, dass die Zahlen aufgerundet oder abgerundet werden sollen? Der iterative Algorithmus befindet sich in der While-Schleife. Dort findet die Prüfung statt. Allerdings nur für eine vom User eingegebene Zahl. Also es werden nicht mehrere Zahlen berechnet. |
|
|
|
Hallo, Du hast den Algorithmus nicht richtig verstanden! Da . ist, mußt Du nur mit der 2 und der 3 testen! Der weitere Test würde mit 5 starten, aber 5 ist größer als 4 und damit muß man nicht weiter testen. Erst ab muß man auch die 5 testen! Am Beispiel: ist weder durch 2 noch durch 3 teilbar, deshalb ist eine Primzahl! PS: Was ist mit dem Test des Programms mit . ? PPS: Habe Deinen letzten Post noch mal genauer gelesen. Unter einem iterativen Algorithmus würde ich eher verstehen, dass eine Funktion sich selbst aufruft. Dass zum Beispiel für Zahlen jenseits der zuerst der Algorithmus abläuft wie gehabt. Für Zahlen jenseits der wird dann mit weiter gemacht aber die Zahlen werden selbst erst mal auf Primzahl getestet und nur wenn sie eine Primzahl sind wird im rufenden Algorithmus die Division auch ausgeführt. Aber das ist hier nicht der Fall. |
|
|
|
Ah, habs jetzt begriffen. Ich werds versuchen in meinem eigenen Programm umzusetzen, um noch effektiver Primzahlen berechnen zu können. Das Programm gibt für aus, dass es sich um eine Primzahl handelt, was natürlich falsch ist. |
|
|
|
Hallo, da stand eben noch ein anderer Text, den hast Du gelöscht, weil Dir vielleicht selber aufgefallen ist, dass zwar durch 7 teilbar ist, aber auch durch 5. Damit ist durch eine Zahl teilbar, die kleiner gleich der Wurzel ist und deshalb ist keine Primzahl. PS: Ich muß jetzt weg, kann erst später am Abend wieder. Wenn es in der U-Bahn funktioniert, dann versuche ich es zwischendurch mit dem Smartphone. Aber das ist anstrengend mit dem Mäusklavier von Tastatur... |
1016093
1016053