Thema: Primzahlcheck

Hi.<P>Also, just 4 fun hab ich auf nem rechner nun seit ~14h ein php prog laufen, das primzahlen berechnet.<P>Er hat mitlerweile ~1.100.470 Primzahlen in einer MySQL db gespeichert, di jetzt schon ~50 Mb gross ist.<P>Das ist aber nicht mein problem.<BR>Ich wollte mal wissen, ob es nicht ein effektiveren Weg gibt, als den, den ich zur Zeit verwende:<P><BR><BLOCKQUOTE><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><HR><pre> <BR>$teiler=1;<BR>$ende=0;<BR>$zahl=3;<BR>$erg=0;<BR>$insert=true;<BR>while (1>0) {<BR>   $starttime=getmicrotime();<BR>   $ende=sqrt($zahl);<BR>   for ($teiler=2;$teiler<=$ende;$teiler++) {<BR>      $erg=$zahl/$teiler;<BR>      if ($erg==floor($erg)) {<BR>         $insert=false;<BR>         break;<BR>      }<BR>   }<BR>   if ($insert==true) {<BR>      //in db<BR>      $endtime=getmicrotime();<BR>      $gesamtzeit=$endtime-$starttime;<BR>      mysql_query("INSERT INTO prim VALUES('','".$zahl."','".$gesamtzeit."')");<BR>   }<BR>   $zahl++;<BR>   $insert=true;<BR>}<BR></pre><HR></BLOCKQUOTE><P>cih denke mal verständlich dürfte der code jedem hier sein.<P>Aber gibbet da nicht was effektiveres, das der rechner mehr zahlen in kürzerer Zeit finden würde???<P>Da er nun bei 17194963 ist, hat er für das finden dieser Primzahl 0.063724994659424 sec gebraucht. Ich will aber das des schneller geht   [img]images/icons/grin.gif" border="0[/img]<P>Jemand ne idee?<P>so long z.<P>Btw:<BR>Ich bin nicht zu dumm, google zu bedienen, habe da aber nix brauchbares gefunden   [img]images/icons/frown.gif" border="0[/img]<p>[ 07.01.2002: Beitrag editiert von: zoro5 ]

GPG key 2E1B4257

Re: Primzahlcheck

Hallole (wieder [img]images/icons/grin.gif" border="0[/img]) zoro,<P>Das Thema wird jetzt fürs WEISSE HAUS wieder einen cholerischen Anfall bedeuten, hehehe&*grins* <I><= Ironische Anspielung</I><P>Aber ich hab da mal eine Primzahl-Zerlegung .. naja schau einfach selbst ...<P>» <A HREF="http://www.devshare.de/cgi-bin/ubb/ultimatebb.cgi?ubb=get_topic&f=10&t=000060" TARGET=_blank>Thread aufrufen</A><P>Grüsse Jochen

Moderator devshare.de | Usability

3

Re: Primzahlcheck

<BLOCKQUOTE><font size="1" face="Verdana, Helvetica, sans-serif">Zitat:</font><HR> der Maximalwert ist:<BR>14.757.395.258.967.641.292<BR>(0xFFFFFFFFFFFFFFFF - 64 Bits)  <HR></BLOCKQUOTE><P>Zitat von wh aus dem genannten Thread.<P>Wie bekommt ich es dann aber hin eine Zahl wie 2^1000000 auf primzahl zu prüfen? Auch wenn der rechner dafür einige wochen braucht. Aber dafür brauch ich des Ja.<P>Diese Zahl, die ich genannte habe, dürfte einige millionen stellen haben.<BR>Das muss gehen.<P>Axo: Der rechner ist ein k6-2 450, 420 mbram, Linux 2.2.19, Slackware 8.0 (was sonst  [img]images/icons/smile.gif" border="0[/img]) und das php als "nice 19" am laufen...<P>so what?<P>so long F.  [img]images/icons/grin.gif" border="0[/img]

GPG key 2E1B4257

Re: Primzahlcheck

erst mal: endlich mal wieder n Post<p>2^10000 ist ganz einfach: kein Primzahl (10000 mal durch 2 teilbar *g*)<p>Maximalwert ist glaub ich (nach "(unsigned LONGLONG) -1") 0xffffffffffffffff = 9344014953780084736 - aber wie kann das gerade sein?<p><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><hr><pre><p>#include "stdafx.h"<p>int main(int argc, char* argv[])
{
    FILE *f;<p>
    unsigned __int64 i = 0;
    i--;<p>
    if (argc > 1) f = fopen(argv[1], "w");
    else f = stdout;
    fprintf(f, "%I64x %I64un", i);
    if (argc > 1) fclose(f);
    return 0;
}<p></pre><hr></blockquote>

mfG whitehouse

Re: Primzahlcheck

@zoro5: du willsts schneller ham? dann lern C! damit gehts garantiert schneller. und: nutz modulo und verzichte auf lahme FPU-Power (ach, Floating-Point halt) (zahl % teiler != 0).

mfG whitehouse

6

Re: Primzahlcheck

<blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Zitat:</font><hr> 9344014953780084736  <hr></blockquote>
na super, hat 19 stellen.
die zahlen mit denen ich rechnen muss, bzw den rechner rechnen lassen muss, sind ~ 4 millionen stellen lang.<p>d.h. so bringt das erstmal nüscht  [img]images/icons/smile.gif" border="0[/img] <p>btw und das 2^100000 keine primzahl ist war mir schon klar. es ging nur darum die länge der zahlenkette darzustellen
eine beispielzahl wäre 2^17194963-1 da wirste es nichtmehr ausm kopf sagen können

GPG key 2E1B4257

7

Re: Primzahlcheck

@ zoro
schnupper vielleicht mal hier:<p>http://www.utm.edu/research/primes/note … index.html<p>gruß<p>matho

Re: Primzahlcheck

@jochen: Wie kannst du nur auf DAS aufmerksam machen *kopfschüttel*. Ich hätte das ein wenig äh du weissssst schon was können.<p>@zoro5: Hehe, dein Posting hat es gerade zu provoziert, dass ich es "widerlege" *g*. Nimm doch den einen Mersenne-Test (GIMPS oder so, wird auch in Mathos Link genannt). Für große Zahlen gibts glaub ich ne Möglichkeit mit Polynomen. ODER SO<p>PS: es gibt in C sowas interessantes
<blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><hr><pre>
typedef union tagLARGEINT {
   struct {
     LONG S1;
     LONG S2;
   } s;
   LONGLONG l;
} LARGEINT;
</pre><hr></blockquote>
in gcc heißts glaub ich "long long" - 64Bit
interessant ist natürlich erst 256Bit *g*<p>[ 13.01.2002: Beitrag editiert von: whitehouse ]</p>

mfG whitehouse

Re: Primzahlcheck

und mein Maximalwer war falsch:
printf("%I64x %I64u", i);
hatte ein i zu wenig:
printf("%I64x %I64u", i, i);<p>0xffffffffffffffff 18446744073709551615 müsste besser stimmen

mfG whitehouse

10

Re: Primzahlcheck

jo, auf das mit den mersenne zahlen läuft das ganze im endeffekt hinaus...<p>hab da ne list gefunden, wonach der server für das prüfen einer zahl ~ 2^10000000-1 ca 160 tage bräuchte    [img]images/icons/smile.gif" border="0[/img]   <p>vielleicht sollte ich dem doch erst nochmal nen athlon XP 2000+ spendieren...<p>der K6-2 450 ist doch etwas lahm, wenn auch mit der besten Distri der welt - Slackware    [img]images/icons/smile.gif" border="0[/img]   <p>so long F.    [img]images/icons/grin.gif" border="0[/img]<p>[ 13.01.2002: Beitrag editiert von: zoro5 ]</p>

GPG key 2E1B4257

11

Re: Primzahlcheck

servus,
du willst das ganze schneller ?
1. schmeiss PHP weg!!
2. lerne C
3. c't 26/01, Seite 51<p>grüsse & fetten segen
manu

Source Code Editor in Perl
http://proton-ce.sf.net

12

Re: Primzahlcheck

moin!<p>zu 1.) nix gegen PHP... absolut endgoil. nur vielleicht ungeeigent für diese aufgabe  [img]images/icons/smile.gif" border="0[/img]
zu 2.) mit c++ hab ich grade erst angefangen, ein paar billige consolen progs zu schreiben
zu 3.) die hab ich nicht  [img]images/icons/frown.gif" border="0[/img]

GPG key 2E1B4257

Re: Primzahlcheck

Hey Leute,
laßt doch mal das C wech! Die einzige Prog-Spache zum ordentlichen Rechnen ist FORTRAN!!!
(das sagt Euch der prom. Ingenieur  [img]images/icons/wink.gif" border="0[/img]  )<p>Gruess Dich math [img]images/icons/smile.gif" border="0[/img]  - Gesundes Neues Jahr wünsche ich Dir.

14

Re: Primzahlcheck

Dasselbe dito!<p>Auf das alle Deine guten Wünsche in Erfüllung gehen.<p>gruß<p>matho

Re: Primzahlcheck

@wintelknecht: Hier geht es NICHT um Rechnen. Hier geht es um Performance! Und FORTRAN ist veraltet. Das sagt dir der junge Schüler. Was ist das eigentlich? (Besonderheiten dieser Sprache?)

mfG whitehouse

16

Re: Primzahlcheck

servus,
fortran... ist (soweit das mein horizont zu lässt)
glaub ich eine sehr hardware nahe sprache... und gerade deswegen...
ES GEHT HIER UM PERFOMANCE
und wenn da fortran besser ist...
allerdings hab ich da net wirklich die AHNUNG...
allerdings sehen progs in fortran für mich recht kryptisch aus. total anderes konzept wie bei sprachen wie c. (hab ich mir mal sagen lassen.. also erzählt mit mehr und berichtigt mich...)<p>
übrigens die Software der vermittlungsstellen werden auch in fortran entwickelt. und ich würde sagen das ist PERFOMACNE UND ZUVERLÄSSIGKEIT BIS IN DEN LETZTEN WINKEL<p>grüsse & fetten segen
manu

Source Code Editor in Perl
http://proton-ce.sf.net

Re: Primzahlcheck

Nur ganz "kurz" - gehört ja eigentlich auch nicht hier her.<p>WH hat recht, wenn er die Variante 77 (oder noch älter) meint. Hier mal ein Auszug aus solch einem Prog:
         if(iret) 142,10,142 --> falls iret<0;=0;>0 dann springe zu marke ...
10      if(idr-3) 12,15,12
12      write(iout,*) f
15      if(istart) 30,18,18
18      iret=0
         do 20 i=1,kk --> entspricht einer for...next schleife, wobei das next bei Sprungmarke 20 steht
         do 20 j=1,kk
20      vl(i+(j-1)*kk)=0.0
         do 24 i=1,kk
         vl(i+(i-1)*kk)=1.0
         vl(kq+i)=abs(swa)
         if(swa) 22,24,24           ! 24,22,22
22      vl(kq+i)=abs(swa*x(i))
24      continue
30      iter=iter+1
*       print*,lo(4,50),'Iterationsschritt : ',iter
         do 32 i=1,kk
         vl(kq2+i)=2.0
32      vl(kq1+i)=0.0
40      ii=1
50      abm=0.0
         do 54 i=1,kk
         aba=vl(kq+ii)*vl(i+(ii-1)*kk)
         abr=abs(aba)/(abs(y(i))+1.e-20)
         if(abr-abm) 54,54,52
52      abm=abr
54      y(i)=y(i)+aba
         if(abm-epsmi) 130,130,56
56      call ziel(y,f1)<p>Wer diesen Code verstehen will, der braucht schon ne Weile dazu. Ein typischer Spaghetti-Code. Der Vorteil: Kurz und schnell.<p>Doch Fortran ist nicht stehengeblieben. Eine wichtige Entwicklung war Fortran 90 (das benutze ich) und dessen konsequente Weiterentwicklung Fortran 95. Wer C (nicht ++) versteht, der versteht auch nahezu jedes Fortran 90 Prog.<p>Fortran 90 unterscheidet sich von den Möglichkeiten her (in Hinsicht auf ingenieurmäßige Belange) in keiner Art von einer anderen modernen Prog-Sprache. Außer expliziten Vererbungsmechanismen (und die braucht man im Normalfall zum Rechnen nicht) und Überladungen stehen alle Möglichkeiten einer sauberen und übersichtlichen Programmierung zur Verfügung. Es stehen weiterhin eine Vielzahl von vordefinierten Routinen zur Verfügung (und damit auch sehr leistungsfähig). In welcher Sprache kann ich einfach:
fMax1=MAXVAL(fFeld1(:,1))
fMin1=MINVAL(fFeld1(:,1))
schreiben und habe sofort den Min/Max-Wert der Spalte 1 des Feldes fFeld1 da? Oder ich schreibe:
fMatrix=MATMUL(fMatrixA,fMatrixB)
und habe das Matrizenprodukt da. Wobei ich einfach vorher definieren kann:
fMatrix=0.0, d.h. ich muß keine Schleife über alle Elemente der Matrix machen. Oder, oder, oder<p>Fortran ist aus meiner Sicht eine fein Sprache um übersichtliche und für den Programmierer komfortable Programme zu schreiben.<p>Achso - die Mechanismen der Mehrprozessorenfähigkeit (die sind dann aber Compilerabhängig) habe ich noch nicht genannt  [img]images/icons/wink.gif" border="0[/img] <p>Was persönliches:
Ich habe 1 Woche vor Abgabe einer Arbeit noch Rechenergebnisse benötigt und war gerade so mit Programmieren fertig. Also Prog gestartet und dann mit Entsetzen festgestellt, das ich ca. 6 Wochen benötigen werde, bis ich alles durch habe. Was nun? Programm hergenommen und auf 3 Workstations und 5 PC verteilt. Bei den PC hab ich die exe natuerlich gleich laufen lassen können. Bei den Großrechnern hab ich die Sache compiliert (gerade auf ner Alpha waren da zwar noch einige Änderungen zu machen, da die 64-bitig rechnen kann, aber im Normalfall eigentlich nicht) und ab gings. Nach 4 Tagen war ich fertig und konnte die Sachen noch auswerten. Und jetzt frage ich: Mit welcher Sprache außer C geht das noch. Mit JAVA vielleicht, mußt aber erst das jdk installieren und brauchst damit admin-Rechte...

Re: Primzahlcheck

hä? Fortran 77 und Fortran 90 hätten dann ja NULL miteinander zu tun. Inwieweit Hardware-nah? Kann mir das mal jemand erklären? Und wozu überhaupt Fortran, was ist der Vorteil?
(OT, aber sonst sagt hier niemand was *g*)

mfG whitehouse

Re: Primzahlcheck

<blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><hr><pre>
double matrix[4][4] = {0};
</pre><hr></blockquote>
- das erste (matrix[0][0]) wird explizit mit 0 initialisiert, die anderen implizit

mfG whitehouse

Re: Primzahlcheck

noch was: normal nutze ich für Non-OOP-Sachen das C ähnliche Subset von C++ (das heißt mit Überladen usw.)

mfG whitehouse

Re: Primzahlcheck

@whitehouse
"...das erste (matrix[0][0]) wird explizit mit 0 initialisiert, die anderen implizit" - gesegnet sei Dein Compiler und Deine Zuversicht in dessen Fähigkeiten.<p>Initialisiere mal die Matrix/den Vektor mit 1.0 und dann verstehst Du, was ich meine.
Im Fortran90 siehts so aus:
real :: fMatrix(10,10), fVektor(10)
fVector=1.0
fMatrix=1.0
Und zwar nicht die jeweils 1. Elemente, sondern alle!<p>Ich hoffe mich jetzt etwas verständlicher ausgedrückt zu haben.<p>Fortran ist zum Rechnen komfortabel (nur zur Info - Ich kann folgende Prog-Sprachen: Fortran, VB/VBA, Java und Pascal - C etwas und C++ noch etwas weniger). Das HTML- und DB-Zeugs laß ich mal wech. D.h. ich kann mir schon ein beschränktes Urteil erlauben.<p>Wenn man einen netten Compiler hat (oder ne Numeric-Bibo und davon gibt es jede Menge) dann kann man z.B. zum Finden der Nullstellen von
p(z) = z^3 - 3z^2 + 4z -2
einfach aufrufen:
CALL ZPLRC (NDEG, COEFF, ZERO)
wobei
- COEFF = (-2.0  4.0 -3.0  1.0) die Koeffizienten sind
- ZERO das Ergebnis der Nullstellensuche ist
- NDEG die Dimension des Polynoms (3) ist<p>Immer noch Fragen warum Fortran? Wenn ja, dann könnte ich Dir auf 90% aller Deiner Mathe-Probleme  eine fertige numerische Lösung bieten. Ich bin zwar ein Freund von selberschreiben, aber manchmal ist so eine nette "kleine" Unterroutine schon sehr hilfreich.<p>Als Hardware-Nah würde ich persönlich Fortran nicht bezeichnen. Das ist ne Frage wie gut oder schlecht der Compiler arbeitet.
Vielleicht "Hardware-Nah" insofern, als dass ich mit Fortran schon mehrere Programme geschrieben habe um aus einer wüsten Binärdatei die Daten rauszuholen. Und das hätte ich mit keiner anderen Sprache machen wollen!!! Geht mit Fortran am einfachsten (sag ich   [img]images/icons/wink.gif" border="0[/img]   ).<p>Achso:
Fortran 90 ist das 77 weiterentwickelt. Alle Sprachelemente von 77 sind in 90 enthalten! Ich kann also ein 77 Prog mit nem 90iger-Compiler übersetzen. Für einige überholte Sprachelemente von 77 wurden in 90 neue geschaffen und die 77iger als obsolescent deklariert. Selbstverfreilich sind in 90 auch noch neue Sprachelemente hinzugekommen.<p>[ 22.01.2002: Beitrag editiert von: wintelknecht ]</p>

Re: Primzahlcheck

Was sind Null-Stellen?
PS: "Gesegenet sei dein Compiler..." - falsch. C sei gesegnet, denn es ist standardisiert, in C++ gibt es noch valarray<p>[ 24.01.2002: Beitrag editiert von: whitehouse ]</p>

mfG whitehouse

Re: Primzahlcheck

Sorry.
Kommt in der 8ten für lineare Funktionen.
Bsp.: Du fährst mit dem Fahrrad konstant 30km/h. Dann ist die Gleichung für den Zusammenhang zwischen Weg s (in km) und Zeit t (in h) s=30*t.<p>Die Nullstelle ist der x-Wert, bei dem y=0 ist (im Bsp. natürlich y==s=0 --> x==t=0).<p>Für s=30*t+5
(das würde bedeuten, dass Du erst zu einem Kumpel fährst, der 5 km entfernt wohnt und Du Deine Losfahrzeit t=0 bei ihm festlegst)
ist die Nullstelle (s=0) hier t=-5/30=-1/6. D.h. Du bist VOR (deshalb das Minus) 1/6h=10min bei Dir zu Hause losgefahren.<p>Und so sieht dann das Diagramm aus:
<blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><hr><pre>
Weg s (in km)
       |
    20 |           *
       |         *
    15 |       *
       |     *
    10 |   *
       | *
     5 *
     * |
__*___|_________________ Zeit t (in h)
  |    0           |
-1/6             1/2
</pre><hr></blockquote>
Gerade in der Darstellung = Lineare Funktion, da
y=a*x^1+b, d.h. x steht selber da. Quadratisch ist es, wenn x^2=x*x da steht usw. usf.<p>Eine lineare Funktion schneidet die y-Achse maximal 1 mal (also da wo y=0).  Maximal deshalb, weil auch kein Schnittpunkt da sein muß (Beispiel: v=30 bedeutet, daß Du konstant 30km/h fährst und weder schneller noch langsamer wirst - Deine Geschwindigkeit v ist somit unabhängig von der Zeit).
Je höher das n bei x^n ist, um so mehr Schnittpunkte hast man mit der y-Achse (maximal n). Und dass kann man dann oftmals nicht analytisch (per Hand) berechnen, sondern nur noch nummerisch.<p>Falls Du das alles schon kanntest, brauchst Du nicht sauer sein, ich wollte es Dir nur anschaulich erklären!<p>Ups, Diagramm verrutscht<p>[ 25.01.2002: Beitrag editiert von: wintelknecht ]</p>

Re: Primzahlcheck

axo, ich kannte den Begriff nur nicht, das heisst also, die Nullstelle von f ist x für das f(x) = 0
für f(x) = mx ist sie natürlich 0 und für f(x) = mx + c ist sie -c/m
Beweis:
f(x) = 0
mx + c = 0
mx = -c
x = -c/m<p>für f(x) = c:
f(x) = 0
c = 0
also entweder allgemeingültig oder inkonsistent<p>[ 26.01.2002: Beitrag editiert von: whitehouse ]</p>

mfG whitehouse

Re: Primzahlcheck

Hallo !<p>Ich weiss nicht, ob ich dir damit helfe, weil ich die div. Links für die Primzahlen, die in diesem Forum genannt wurden angeschaut habe, aber vielleicht ja doch.
Ich habe ein Primzahlenprogramm unter http://members.chello.at/robert.weixelb … zahlen.htm welches nicht nur die geraden Zahlen beim Primzahlentest überspringt, sondern auch die die durch 3 und 5 teilbar sind. Dieses Programm sollte exakte Ergebnisse liefern. Für sehr grosse Primzahlen kann man den Primzahltest von Rabin verwenden, den ich allerdings nicht näher kenne. Er liefert aber keine exakten Ergebnisse, sondern sagt nur aus, das eine Primzahl mit sehr hoher Wahrscheinlichkeit eine Primzahl ist.<p>mfG Robert