8-Bit-Nirvana Startseite  
?OUT OF MOTIVATION ERROR IN 30130
[ Home | Index | Werbung | Forum | Flohmarkt | Gästebuch | Links | Info ]

8-Bit-Forum

"Re: Primzahlenproblem" von Sascha Hoogen
(12.1.2000, 18:42)

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

Bezugsnachricht: Re: Primzahlenproblem (Thorsten Nickel)
Antworten: Re: Primzahlenproblem (Ullrich von Bassewitz)
Re: Primzahlenproblem (georg)
Re: Primzahlenproblem (Thorsten Nickel)

[ Antwort schreiben | Übersicht | Thema ]

Thorsten Nickel schrieb am 12.1.2000, 08:28:25:

> > (siehe
> > Listing 2 mit dem eigens dafür angelegten Array). Da die ersten Tests sowieso
> > die häufigsten Teiler (2, 3, 5 und 7) checken, wäre ein evtl. möglicher
> > Geschwindigkeitsgewinn wohl eher gering. Aber ich lasse mich durch ein
> > entsprechendes Listing gerne überzeugen. :)
>
> fuer grosse Primzahlen durchaus, wenn der Ausschlauss der 5 an der
> Einerstelle wirklich effizient implementiert ist.
> fuer jede Primzahl laesst sich halt exakt angeben, wieviel
> Teiler mit einer 5 an der Einerstelle getestet werden
> (Groessenordnungsmaessig: (P^0.5)/5, p sei prim)

Wie gesagt, ein entsprechendes Listing überzeugt mich dann auch von der
effizienten Implementierung. ;)

> > > (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 )
> >
> > Das ist allerdings eine geradezu geniale Verkürzung! :) Klar, Teiler
> > größer als SQR(Testzahl) muß man gar nicht erst berücksichtigen.
>
> naja, man koennte auch die wurzel nehmen vom Primzahlkandidaten und
> und mit dem Testteiler vergleichen.

Macht eigentlich kaum einen Unterschied, Quadrieren dürfte aber etwas schneller
gehen als Wurzelziehen (müßte ich nachprüfen, ist nur eine Vermutung).

> > > einfachste Idee: haeng den Primzahlalgo 4 mal hintereinander.
> > > in den 4 Teilen werden jeweils die Teiler mit Einerstelle 1,3,7,9
> > > durchlaufen.
> >
> > Igitt, wie unelegant! Mir stinkt schon das Verzichten auf FOR...NEXT und
> > IF...THEN aus Performancegründen. ;))
>
> naja, es ist die simelste Umsetzung, das laesst sich natuerlich
> mit 2 gosub spruengen zu 2 im prinzip identischen algos effizient verkuerzen.
[...]
> die gosub variante ist noch am effiezientesten, weil sie nix zusaetzliches kostet

GOSUB effizient? Nee, GOSUB...RETURN ist wirklich ein Performancekiller.

> > Wenn eine Modulo-Funktion vorhanden ist, dann isses recht einfach:
> > I=I+2-2*(MOD(I/10)=3)
>
> tja, MOD als unterprogramm zu simulieren,ist aber tuerer als schlicht
> 2 zu addieren oder die gosub-variante (1,3, 7,9) zu verwenden

Würde mich nicht wundern, wenn in dem einen oder anderen aufgemotzten
Basic-Dialekt MOD bereits enthalten ist (kennt jemand einen?). Beim C64
ist dem aber natürlich nicht so... ;)

> > > Thorsten (, der mal das Fermatproblem fuer n>=3 versucht hat
> > > zu implementieren,huuua haha, lang ists´ her ;-)
> >
> > Was ist denn das für ein Problem? Klingt ein wenig wie Ausschlag an
> > ungünstig gelegenen Körperteilen... ;))))
>
> a^n+b^n=c^n ist bekanntlich Phytagoras fuer n=2
> alle erfuellende tripel a,b,c aufzuzaehlen ist simpel, gibt
> eine schoene "Formel" oder halt brute force ;-)

Damit könnte man seinen Rechner bestimmt schön für Jahrhunderte beschäftigt
halten... ;)

> fuer n>2 war seit einigen Hundert jahren fuer bestimmte n gezeigt
> worden, dass keine Loesung existiert. Fermat gab im 16. Jhd. an einen
> Beweis zu kennen, aber erst 1993/1994 konnte der Englaender Wiley
> den endgueltigen Beweis erbringen, dass es keinen Loesung gibt
>
> Als Schueler hab ich halt die Phytagoreischen Zahlentripel fix
> runter programmiert und angenommen, dasses fuer n>2 auch Loesungen
> gaebe... wenn der Zahlenbereich nicht so mickrig waere, liefe
> mein Prog heute noch ;-)

Dann hättest Dir wohl spätestens heute gedämmert, daß wahrscheinlich
kein Lösung existiert. ;))

Tschö,
Sascha


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 ]