8-Bit-Nirvana Startseite  
?CRAY INFERIORITY COMPLEX ERROR IN 34810
[ Home | Index | Werbung | Forum | Flohmarkt | Gästebuch | Links | Info ]

8-Bit-Forum

"Re: Primzahlenproblem" von Sascha Hoogen
(10.1.2000, 21:04)

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

Bezugsnachricht: Primzahlenproblem (Stefan Derer)
Antworten: Re: Primzahlenproblem (Thorsten Nickel)

[ Antwort schreiben | Übersicht | Thema ]

Stefan Derer schrieb am 10.1.2000, 19:05:05:

> Ich suche ein Basic-Programm, welches mir die Primzahlen ausgibt.
> Ich hab es ein paarmal nebenbei versucht zu schreiben, aber jedesmal
> hatte ich nen Denkfehler drin. Hab mich allerdings auch nicht übermäßig
> darüber gesetzt.
> Hat einer ne gute Quelle? Oder hat einer ne Idee für die korrekten
> Programmzeilen?

Eine Möglichkeit wäre z.B. die folgende, sehr simple Methode:

10 P$(0)="PRIMZAHL"
20 P$(1)="TEILBAR"
30 I=2
40 I=I+1
50 J=1
60 J=J+1
70 C=-(I/J)=INT(I/J))
80 ON -((J<I-1)+C) GOTO 60
90 PRINT I;": ";P$(C)
100 GOTO 40

Es wird einfach die Variable I hochgezählt und dann geguckt, ob sie durch
eine Zahl von 2 bis I-1 teilbar ist (Variable J). Das ist Brute Force und
zeigt auch sehr schnell auf, wie langsam Basic doch ist... ;)

Eine etwas elegantere Möglichkeit wäre folgende, allerdings ist sie immer
noch Brute Force:

10 DIM P(10000)
20 P=0:P(0)=2
30 P$(0)="PRIMZAHL"
40 P$(1)="TEILBAR"
50 I=2
60 I=I+1
70 J=-1
80 J=J+1
90 C=-(I/P(J)=INT(I/P(J)))
100 ON -((J<P)+C) GOTO 80
110 PRINT I;": ";P$(C)
120 ON C GOTO 60
130 P=P+1:P(P)=I
140 GOTO 60

Der Unterschied zum ersten Progrämmchen besteht darin, daß die gefundenen
Primzahlen gespeichert werden und I dann nur auf Teilbarkeit durch diese
gespeicherten Primzahlen getestet wird. Dadurch spart man schon tüchtig
Rechenzeit, dafür kostet diese Möglichkeit auch deutlich mehr Speicher.

Die Sache ließe sich noch weiter optimieren, z.B. müßte man nicht durch
Primzahlen teilen, die größer als I/2 sind. Da gibt´s sicher noch deutlich
intelligentere Algorithmen, bloß fallen die mir im Moment nicht ein. ;)

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 ]