Schriftliches Rechnen < Anwendungsprogramme < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:19 Fr 16.03.2007 | | Autor: | nitrosio |
Guten Tag. Ich möchte gerne ein Programm (in QBasic) entwickeln, mit dem ich möglichst grosse Primzahlen berechnen kann. Jetzt möchte ich nicht den MOD-Befehl verwenden und bei einer normalen Division hat der Teiler eine maximale Grösse von 200'000'000. Das ist mir aber zu wenig; ich möchte (wenigstens auch nur theoretisch) mit mehreren Millionen Kommastellen und entsprechend grossen Textstrings arbeiten. Jetzt meine frage: wie mache ich das genau; wie kann ich schriftlich eine Zahl durch einen möglichst grossen Divisor teilen? Kann mir da jemand weiterhelfen? Vielen Dank.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:19 Fr 16.03.2007 | | Autor: | Ankh |
Divident : Divisor = Quotient
Sei a, der Divident, m-stellig und b, der Divisor, n-stellig und c der Quotient.
Bezeichne [mm] x_i [/mm] die i-te Stelle einer Zahl.
Dann müsste die Rechnung ungefähr so ablaufen:
Falls m < n, dann c = 0,..., weiterrechnen mit a*10.
Für m>n: suche das minimale k so dass [mm] a_1a_2...a_k \ge [/mm] b gilt. Die nächste Stelle [mm] c_i [/mm] ergibt sich aus [mm] $[a_1a_2...a_k [/mm] : b] [mm] \in \{1, ..., 9\}$.
[/mm]
Weitermachen mit [mm] (a_1a_2...a_k [/mm] - [mm] (c_i *b))*10+a_{k+1}.
[/mm]
Abbruchbedingung: [mm] a_1a_2...a_k [/mm] - [mm] (c_i [/mm] *b) = 0.
Für m=n: Testen, ob a < b gilt und entsprechend Fall 1 oder 2 abarbeiten.
Wenn a, b keine Primzahlen sind, ist es sinnvoll mit Primfaktorzerlegung zu arbeiten.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:16 Fr 16.03.2007 | | Autor: | nitrosio |
Vielen Dank für deine Antwort, Ankh. Ich muss wohl also ganz normal vorgehen; d.h. ich ich nehme so viele Stellen vom Dividenten, bis ich ihn teilen kann bzw. bis der Divisor mindestens drei mal reinpasst, nehme den abgerundeten Quozienten als erste Stelle des Ergebnises, nehme den Rest und hänge die nächsten Stellen Dividenten dran, so dass ich auch dies wieder teilen kann usw. Ich muss also mit jeder einzelnen Ziffer arbeiten und dieser eine eigene Variable zuweisen; auch der Primzahlennummer (mit einem Roboter und viele Schleifen). Demnach ist eine Division wohl immer ein Produkt aus Multiplikation (Addition) und Subtraktion. Mit Faktorzerlegung arbeite ich lieber nicht, da das bei grossen Zahlen relativ lange dauert. Das Prinzip des Programmes ist mir wenigstens auch schon mal klar: ich nehme eine Zahl und schaue, ob diese durch eine kleinere Primzahl (3, 5, 7, 11) teilbar ist (bis zur Quadratwurzel), und speichere (falls das dann eine Primzahl ist) diese dann in einer sequentiellen Datei unter einer Variablen ab. Danach nehme ich die Zahl und addiere zwei dazu... Ich habe hier schon mal ein gutes Programm geschrieben, allerdings funktioniert das noch mit MOD und teilt die Zahl durch jede ungerade Zahl bis zur Wurzel, falls sie vorher nicht teilbar ist. Ist jedenfalls recht schnell; im Gegensatz zum Primzahlensieb, Additionsmethode etc.
zahl = 3: teiler = 3
DO
'wenn prim
IF SQR (zahl) < teiler THEN PRINT zahl; : zahl = zahl + 2: teiler = 3
'wenn teilbar
IF zahl MOD teiler = 0 THEN zahl = zahl + 2: teiler = 1
IF zahl > 1000 THEN END
teiler = teiler + 2
LOOP
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:21 Fr 16.03.2007 | | Autor: | Ankh |
Du musst nicht unbedingt den ganzen Divisor verwenden:
Angenommen, a und b sind beide m-stellig mit a>b.
Dann weißt du sicher, dass [mm] $[\bruch{a_1}{2b_1}] \le [/mm] c [mm] \le [\bruch{a_1}{b_1}]$.
[/mm]
Je mehr Stellen du betrachtest, um so genauer kannst du c einschachteln. Unter Umständen musst du dann nicht alle Stellen berücksichtigen.
Der Fall a [mm] \not= [/mm] b lässt sich sicher analog meistern.
|
|
|
|
