Größter gemeinsamer Teiler mehrerer Zahlen

Maxi

Hi!

Wie kann man am schnellsten den GGT von mehreren Zahlen bestimmen? Es sind 20 zahlen. Mit zweien gehts ja schnell mit dem Algorithmus nach Euklid. KAnn man den auch auf mehrere Zahlen anwenden?

Abbadon

ich glaub es gilt: ggT(a,b,c) = ggT(ggt(a,b),c) (bin mir aber nicht ganz sicher, hab mal das gegenteil behauptet), du könntest also so den ggT rekursiv mit hilfe des euklidschen Algoritmus berechnen, aber ob das die schnellste Methode ist...

Maxi

Hab dann doch noch was gefunden, dauert bei großen zahlen aber auch relativ langsam:

int main()
{
   unsigned long a,b;
   printf("ggt = größter gemeinsamer Teiler(mit 0 beenden)\n");
   printf("Zahl> ");
   scanf("%lu", &a);
   printf("Zahl> ");
   scanf("%lu", &b);
   a=ggt(a, b);
   while(1)
      {
         printf("Zahl> ");
         scanf("%lu", &b);
         if(b==0)
            break;
         a=ggt(a, b);
      }
   printf("-------->ggt = %lu\n", a);
   return 0;
}

ERROR

grunsätzlich kannst du die zahlen in primfaktoren zerlegen

und dann bekommst du den ggt raus, wenn du die regel beachtest:

die faktoren, die in allen zerlegungen vorkommen, werden multipliziert
und ergeben den ggt

bsp. für drei zahlen:

12 24 36

12= 3 * 4
24= 3 * 4 * 2
36= 3 *4 *3
________________
ggt=3 * 4

so und da sollte recht einfach zu machen sein, wenn du einen schnellen algo für die primfaktorzerlegung hast, sollte das auch relativ schnell sein

naja nur so als grundsätzliche verfahrensweise

cu

Maxi

hm, danke, werds mal ausprobieren

Nimda

Man kann den Euklid'schen Algorithmus auf mehrere Zahlen erweitern:
ggT(ggT(a,b),c)=ggT(a,b,c)
Das ist meißtens schneller als Primfaktorzerlegung. Am langsamsten ist der Euklid'sche Algorithmus bei zwei aufeinanderfolgenden Fibonacci-Zahlen(0,1,1,2,3,5,8,13,21,34,...)

Ich hab das nachgeschlagen in: Kleine Enzyklopädie Mathematik
(Klein? Das Teil hat 800 Seiten mit jeweils 60 Zeilen!)