• Herkunft: Wien
  • Registrierungsdatum: 28-07-2001
  • Beiträge: 117

Re: Primzahlcheck

Hallo !<p>Zu meiner vorigen Antwort eine Korrektur. Ich habe mir die div. Links nicht angeschaut.<p>Ich hätte eine weitere Idee den Algorithmus zu verbessern. Im Unterschied zu meinem Programm, wo ich eine Zahl in ein Formular eingebe, bräuchtest du von Anfang an nur die Zahlen zur Überprüfung heranziehen, die nicht durch 2, 3 und 5 teilbar sind. Da es sich ja um sehr viele Zahlen handelt, könnte man die Zahlen, die durch 7, 11, 13, usw. teilbar sind auch von vorneherein überspringen.
Bei der Zahl durch die du dividierst gehts du genauso vor. Und dividieren bräuchtest du die Zahl überhaupt nur durch die bereits gefundenen Primzahlen, hat aber wohl nur dann einen Sinn, wenn sie noch im Hauptspeicher sind und nicht von der Datei gelesen werden müssen.<p>mfG Robert

Robert2718's Webseite

  • Herkunft: D-BaWü Ulm
  • Registrierungsdatum: 21-03-2001
  • Beiträge: 1.727

Re: Primzahlcheck

tut mir leid, aber deine Methode ist doch Blödsinn ... ob ich die Zahlen in einem if teste, oder ob ich n for bemühe ist doch herzlich egal! daher: (das ist die beschissenste Methode)
<blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><hr><pre>
pz = true;
for (i = 2; i <= intsqrt(zahl); i++)
   if (zahl % i) {
     pz = false;
     break;
   }
/*
pz ... true - prim / false - unprim
intsqrt(x) ist eine Funktion wie Math.floor(Math.sqrt(x)) bzw. (int)sqrt(x)
*/
</pre><hr></blockquote><p>[ 03.02.2002: Beitrag editiert von: whitehouse ]<p>[ 03.02.2002: Beitrag editiert von: whitehouse ]</p>

mfG whitehouse
  • Herkunft: D-BaWü Ulm
  • Registrierungsdatum: 21-03-2001
  • Beiträge: 1.727

Re: Primzahlcheck

<blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><hr><pre>
for (i = 2; i < max; i++)
   arr[i] = i;
for (i = 2; i < max; i++)
   for (j = 2*i; j < max; j += i)
     arr[j] = 0;
for (i = 2; i < max; i++)
   if (arr[i])
     printout(arr[i]);
</pre><hr></blockquote>

mfG whitehouse

29 Antwort von HAL9000

  • Herkunft: Innsbruck
  • Registrierungsdatum: 11-02-2002
  • Beiträge: 9

Re: Primzahlcheck

das schnellste um primzahlen effektiv und in unbegrenzter Größe zu berechnen ist

1. sich eine ASM-Anwendung zu schreiben
2. nur register und keine Variablen für die eigentlichen Rechenoperationen verwenden
3. sich von einem zweiten Prozessor während der Berechnungen möglichst viele Priemzahlen schicken lassen (die höchsten die berechnet wurden, sich aber unter der Wurzel der nächsten zu berechnenden Zahl befinden)

Punkt 3 kann natürlich nicht jeder, aber auch ohne Punkt drei ist man mit dieser Methode um ein vielfaches schneller als mit Fortran, c oder anderen hohen Sprachen.

Gerade Zahlen nicht überprüfen (das sollte wohl eh klar sein, oder?)
Zahlen deren Quersumme durch drei teilbar sind sind auch selbst durch drei teilbar.
Ich glaube daß es da noch ein paar solche schmähs gibt.

HAL9000's Webseite

  • Herkunft: D-BaWü Ulm
  • Registrierungsdatum: 21-03-2001
  • Beiträge: 1.727

Re: Primzahlcheck

Ich geh das mal ab...
  </font><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Zitat:</font><hr /><font size="2" face="Verdana, Helvetica, sans-serif"> 1. sich eine ASM-Anwendung zu schreiben </font><hr /></blockquote><font size="2" face="Verdana, Helvetica, sans-serif">- nuja, bei nem guten Compiler bringt das wenig und macht viel Mehraufwand. Manchmal wird C als eine Art Makro-Assembler angesehen...

  </font><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Zitat:</font><hr /><font size="2" face="Verdana, Helvetica, sans-serif"> 2. nur register und keine Variablen für die eigentlichen Rechenoperationen verwenden
  </font><hr /></blockquote><font size="2" face="Verdana, Helvetica, sans-serif">- das is klar, aber nich immer unbegrenzt möglich, in C bspw. gibt es das "register", das bei Möglichkeit auf ein Register umsetzt.

  </font><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Zitat:</font><hr /><font size="2" face="Verdana, Helvetica, sans-serif"> 3. sich von einem zweiten Prozessor während der Berechnungen möglichst viele Priemzahlen schicken lassen (die höchsten die berechnet wurden, sich aber unter der Wurzel der nächsten zu berechnenden Zahl befinden)
  </font><hr /></blockquote><font size="2" face="Verdana, Helvetica, sans-serif">- naja, du hast selten die Möglichkeit, das allein zu entscheiden. Habe du lieber das richtige OS (Unix/Linux, dev0 würde aber für Windows NT plädieren *g*) und setze Threads ein, die dann ja auch verteilt werden können.

  </font><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Zitat:</font><hr /><font size="2" face="Verdana, Helvetica, sans-serif"> Punkt 3 kann natürlich nicht jeder, aber auch ohne Punkt drei ist man mit dieser Methode um ein vielfaches schneller als mit Fortran, c oder anderen hohen Sprachen.
  </font><hr /></blockquote><font size="2" face="Verdana, Helvetica, sans-serif">- jetz übertreib mal nich *g*, vielleicht 1,7 so schnell, aber so viel schneller als C... kaum möglich. (Ausser du bist ein Ultra-Maesto-ASM-Coder...)

   </font><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Zitat:</font><hr /><font size="2" face="Verdana, Helvetica, sans-serif"> Gerade Zahlen nicht überprüfen (das sollte wohl eh klar sein, oder?)
</font><hr /></blockquote><font size="2" face="Verdana, Helvetica, sans-serif">- BLÖDSINN. Wenn ich sowieso als erstes zwei überprüfe, macht das keinen Unterschied.

   </font><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Zitat:</font><hr /><font size="2" face="Verdana, Helvetica, sans-serif"> Zahlen deren Quersumme durch drei teilbar sind sind auch selbst durch drei teilbar.
Ich glaube daß es da noch ein paar solche schmähs gibt.  </font><hr /></blockquote><font size="2" face="Verdana, Helvetica, sans-serif">- theoretisch wahr, aber bis du die Zahl in in nen "String" (im numerischen Sinne, einfach ein Polynom) und von dem dann die Quersumme hast, hast du zehnmal Modulo gemacht.

Nichtsdestotrotz bin ich froh, dass manche sich trotz meiner Kommentare  <img border="0" title="" alt="[Winken]" src="images/icons/wink.gif" />  "trauen" etwas zu dem Thema hier zu äussern.

mfG whitehouse