007
23.04.2003, 17:13 Uhr
~0xdeadbeef
Gast
|
OK, hier kommt der Bugfix:
Tauscht den Test auf zahl>1 gegen faktor*faktor<=zahl aus. Hintergrund ist der: Wenn der Faktor bei Wurzel(zahl) (also des Restes) angekommen ist, ist der Rest schon nicht mehr durch alle Zahlen, die kleiner als Faktor sind, teilbar - die haben wir nämlich vorher schon rausgehauen. Wenn eine Zahl durch keine Zahl kleiner oder gleich ihrer Wurzel teilbar ist, ist sie nach Schulmathe eine Primzahl. Et voila, wir haben unseren großen Primfaktor. Den Test darauf, ob zahl > 1 ist, können wir uns dann sparen, weil in dem Moment, in dem zahl bei eins ankommt, faktor*faktor mit Sicherheit größer als Zahl ist. Hier kommt das fertige Programm:
C++: |
#include <stdio.h>
void print_primefactors(unsigned long long zahl) { unsigned long long faktor; printf("%llu:\t", zahl); while(zahl % 2 == 0) { printf("2 "); zahl /= 2; } for(faktor = 3; faktor*faktor <= zahl; faktor += 2) while(zahl % faktor == 0) { printf("%llu ", faktor); fflush(stdout); zahl /= faktor; } if(zahl > 1) printf("%llu", zahl); printf("\n"); }
int main(int argc, char *argv[]) { unsigned long long zahl; int i; if(argc > 1) { for(i = 1; i < argc; ++i) { sscanf(argv[i], "%llu", &zahl); print_primefactors(zahl); } } else { printf("Zahl eingeben: "); scanf("%llu", &zahl); print_primefactors(zahl); } return 0; }
|
Mann, bin ich gut! ...und ich habe zuviel Freizeit... |