Größter gemeinsamer Teiler mehrerer Zahlen



  • 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?



  • 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...



  • 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;
    }
    


  • 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



  • hm, danke, werds mal ausprobieren



  • 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!)


Anmelden zum Antworten