Algorithmus zur Primzahlbestimmung?
Wie kommt man darauf, dass man bei Algorithmen um alle Primzahlen von 2 bis n zu finden es genügt zu schauen, ob es unter den ersten Zahlen einen Divisor von n gibt? Daran denkt man doch nicht beim implementieren eines Algorithmus. Kann ich einfach nicht logisch genug denken?
3 Antworten
Daran denkt man doch nicht ...
Daran habe ich schon gedacht, als ich meinen ersten programmierbaren Taschenrechner hatte und ihn mal quälen wollte. Vor ca. ½ Jahrhundert.
Ja, damals mußte man noch auf Effizienz beim Programmieren achten, weil die Kisten so langsam rechneten.
Als ich so ungefähr zur selben Zeit das erste Mal einen Simpson programmiert habe, lief das so langsam, daß ich mir eine Optimierung überlegte, die es möglich macht, keinen Punkt zweimal zu berechnen wenn man die Zahl der Stützpunkte in jedem Durchlauf verdoppelt. Ein paar Tage lang fühlte ich mich wie der König der Welt, weil das Ding dann doppelt so schnell lief. ☺
Würdest Du es naïv programmieren, so daß Du zur Teilbarkeit alle Zahlen 2,3,4,…,N−1 durchprobierst, dann würdest Du bei ein paar Testläufen sehr rasch merken, daß das uneffizient ist.
- Du würdest z.B. bemerken, daß jede zusammengesetzte Zahl bei einer Division durch eine Primzahl erkannt wird, niemals bei einer Division durch eine zusammengesetzte Zahl — denn wenn Deine Testzahl von irgendeiner zusammengesetzten Zahl geteilt wird, dann gibt immer einen Primteiler, der das auch kann und sogar noch kleiner ist. Also reicht es, durch Primzahlen zu dividieren.
- Aber selbst dann würdest Du bemerken, daß die erste Zahl, die die Testzahl teilt, immer ziemlich klein ist. Da kommt man dann rasch zum Schluß, daß man die großen Zahlen vielleicht gar nicht zu testen braucht, und mit ein bißchen Nachdenken stellt man dann fest, daß √N ausreicht.
Wenn es zwei Divisoren k und l von n gibt, also k*l = n, dann muß einer der beiden kleiner oder gleich wurzel(n) sein. Denn wurzel(n)*wurzel(n) = n.
Üben, üben, und nochmal üben. Ich habe zu Beginn meines damaligen Informatikstudiums gedacht ich lerne das Beweisen nie. Am Ende hat mir das so viel Spaß gemacht dass ich auf Mathematik gewechselt habe. Wenn man genug übt sieht man solche Gedankengänge sofort.
Im Endeffekt würde ich sagen. Mathematische Kreativität. Das ist ungefähr so als würde man fragen wie ein Tolkien auf eine so grandiose Geschichte kommt.
So wie Roll es erklärt hat ist es ja durchaus offensichtlich.
Aber ersteinmal drauf zu kommen erfordert ein entsprechend Tiefgreifendes mathematisches verständnis und man muss damit etwas rumspielen. Mit der Zeit bekommt man ein gefühl dafür.
Du implementierst das mal, schaust Dir den Output an, dann kommst Du schon drauf.
Danke, aber das habe ich schon verstanden. Meine Frage war vielleicht etwas unklar gestellt, aber ich habe mich gefragt, wie man eine solche Problemlöseföhigkeit entwickelt, das man selber ad hoc auf solche Dinge kommt. Selber eingefallen wäre mir diese clevere Eingrenzung nie.