Allgemeine Programmiertheorie
-
Hallo liebe C-Experten,
Ich habe hier ein schon eher schwierigeres Programm, welches zu einer Zahl n immer die Primfaktoren bestimmt. Auf Anhieb bin Ich mit der Entschlüsselung noch leicht überfordert. Es läuft - funktioniert aber einwandfrei. Es bestimmt die Primfaktoren scheinbar, indem es auch bei größeren Primzahlen zuerst die Primzahlen selbst bestimmt. Da es z.B eine Primzahl wie die 457 nicht gespeichert hat, kann aber diese Zahlen als Primfaktoren auch bei großen Zahlen sofort ausgeben, auch wenn man sehr große Primzahlen wie 999983 oder 7129 hoch 2 eingibt, gibt es deren Primfaktoren (999983 hoch 1) sofort aus. Dies müsste doch eigentlich mit der hohen Rechenleistung des Computers einhergehen, da es doch eigentlich alle Zahlen durchprobieren muss, wenn die Primzahlen größer werden ??Hier zur Veranschaulichung das Programm:
/* Primfaktorzerlegung einer positiven natuerlichen Zahl n */ #include <stdlib.h> #include <stdio.h> void div_potenz(unsigned int *, unsigned int); int main( ) { unsigned int n,i,l; unsigned int r[3]={2,3,5}, q[8]={7,11,13,17,19,23,29,31}; printf("\nBerechnung der Primfaktorzerlegung \ von n\n\n"); printf("n = "); scanf("%u",&n); if (n!=1) { printf("Die Primfaktoren von %u sind:\n\n",n); for (i=0; i<3; i=i+1) { div_potenz(&n,r[i]); } l=0; do { for (i=0; i<8;i=i+1) { div_potenz(&n,30*l+q[i]); } l=l+1; } while ((30*l+7)*(30*l+7)<=n); if (n>1) { printf("%u Exp.: 1\n",n); } } exit(EXIT_SUCCESS); } /* Pruefen, ob p|x, Bestimmen und Herausdividieren der * groessten p-Potenz */ void div_potenz(unsigned int *x, unsigned int p) { unsigned int e=0; while (*x%p==0) { e=e+1; *x=*x/p; } if (e>0) { printf("%u Exp.: %u\n",p,e); } }
-
softpad schrieb:
sofort ausgeben, auch wenn man sehr große Primzahlen wie 999983 oder 7129 hoch 2 eingibt, gibt es deren Primfaktoren (999983 hoch 1) sofort aus. Dies müsste doch eigentlich mit der hohen Rechenleistung des Computers einhergehen, da es doch eigentlich alle Zahlen durchprobieren muss, wenn die Primzahlen größer werden ??
Beachte, daß er die Teiler nur bis zur Wurzel der Zahl testen muss!
Bei N=999983 nur bis 999. Wäre ein Teiler P größer als die Wurzel, so wäre Q=N/P eine ganze Zahl also auch Teiler und kleiner als die Wurzel.
So ein Schleifchen bis 1000 schafft der Computer schnell.
Aber hast schon recht, für sehr große Zahlen mit hunderten von Bits ist das Verfahren völlig ungeeignet, zu lahm.Übrigens hat er den netten Beschleunigungstrick http://primes.utm.edu/glossary/xpage/WheelFactorization.html benutzt.
-
Danke !