8-Bit-Nirvana Startseite  
?FED UP WITH BASIC ERROR IN 43540
[ Home | Index | Werbung | Forum | Flohmarkt | Gästebuch | Links | Info ]

8-Bit-Forum

"Re: Primzahlenproblem" von Thorsten Nickel
(11.1.2000, 10:09)

(Dieser Artikel wurde 1221 mal seit dem 16.10.2001, 22:56 aufgerufen)

Bezugsnachricht: Re: Primzahlenproblem (Sascha Hoogen)
Antworten: Re: Primzahlenproblem (Sascha Hoogen)

[ Antwort schreiben | Übersicht | Thema ]

Auch muesste ein Primzahlkandidat nur mit ungraden Teilern getestet werden, wobei Teiler mit einer 5 an der Einerstelle gar nicht infrage
kommen. (Warum ? ... ,....)

Nur ist eine Abfrage beim Teiler, ob eine 5 an der
einer Stelle vorliegt genauso teuer, als wenn unnoetigerweise mit
solch einem Teiler die Primzahl-eigenschaft getestet wird.

(Einschub:
Natuerlich muss auch nur bis zur Wurzel des Primzahlkandidaten
getestet werden. Trick hier: quadriere den Teiler und schau, ob
er grosser gleich ist dem Primzahlkandidaten.
Bsp: 49=7*7, 21=3*7 )

Ausweg: kompletter Basenwechsel, weg vom Dezimahlsystem zu einem
geeigneteren Zahlensystem, waehrend beim 10er-System die 2 und die 5 unnoetig zu testen sind an der Einerstelle, kann man bei einem Basenwechsel daruber hinaus noch andere Teiler einsaparen...

Bleibt man beim Dezimalsystem , so beobachtet man bei den notwendiger
weise ungraden Teilern die zyklische sich wiederholende Folge 1,3,7,9 (ohne die 5)

von 1 nach 3 betraegt die Differenz 2 ,
von 7 nach 9 betraegt sie ebenfalls 2,
nur von 3 nach 7 ist sie 4 , da 5 als Einerstelle beim Teiler unsinnig
ist.

Mit einb bischen Knobeln bekommt man effiezienten Basic Code hin, dass das Einsparen der 5 nicht mit zusaetzlichem Rechenaufwand erkauft werden muss.

einfachste Idee: haeng den Primzahlalgo 4 mal hintereinander.
in den 4 Teilen werden jeweils die Teiler mit Einerstelle 1,3,7,9
durchlaufen.

moechte man das Primzahlprogramm nicht 4 mal hintereinander haengen,
muss man die Teiler mit der Endstelle 1,3,7,9 berechnen ohne "zuviel"
Rechenzeit zu verbrauchen.

es geht..., ist aber raffiniert ;-)

hach, waren das Zeiten , als sich Zahlentheorie noch so intuitiv
angehen liess ...

Gruss & viel Spass, den hat man damit wirklich :)

Thorsten (, der mal das Fermatproblem fuer n>=3 versucht hat
zu implementieren,huuua haha, lang ists´ her ;-)


Lesezeichen für diesen Beitrag: del.icio.us del.icio.us Bei Mister Wong speichern Mister Wong Seite bei LinkARENA speichern LinkARENA Digg it Digg Slashdot it Slashdot StumbleUpon StumbleUpon


Antwort schreiben

Hier kannst Du auf die angezeigte Nachricht antworten. Beachte bitte die folgenden Punkte:
  • Dieses Forum befasst sich ausschließlich mit 8-Bit-Computern und Videospielen, Artikel zu anderen Themen sind off-topic und unerwünscht (für Computer mit mehr als 8 Bit gibt es hier aber auch ein eigenes Forum). Wenn der Vorschreiber schon vom Thema abweicht und Du unbedingt antworten möchtest, dann schreibe ihm lieber per e-mail.
  • Schreibe bitte so, dass sich niemand beleidigt oder angegriffen fühlt, auch wenn der Vorschreiber sich bereits im Ton vergriffen haben sollte. Solche Sachen löst man eh besser privat per e-mail.
  • Im Eingabefeld wird der komplette Text zitiert. Kürze die Zitate bitte so weit wie möglich, damit unnötiger Ballast vermieden wird. Hinweise zu richtigem und falschem Quoting findest Du hier: learn.to/quote.
Name:
E-mail:
Betreff:
Antwort:
Klicke bitte das Feld links an, falls Du Antworten auf diese Nachricht auch per E-mail bekommen möchtest.


       

Achtung: "SPAMFALLE" heißt nicht ohne Grund so, keinesfalls benutzen!



Mozilla Sidebar Opera Sidebar RSS 0.91 Newsfeed RSS 2.0 Newsfeed Add to Google Add to MyYahoo Spam Poison
Mozilla Sidebar Opera Sidebar RSS 0.91 Feed RSS 2.0 Feed Add to Google My Yahoo! Spam Poison

[ Index | Werbung | Forum | Flohmarkt | Gästebuch | Links | Info | Impressum/Datenschutz | News | Credits | Webmasters | Seitenanfang ]