Größter gemeinsamer Teiler: mein Code

[JavaLernen1]

Hallo und einen schönen Sonntag!
Aus Übungszwecken habe ich mal eine Methode geschrieben, die den größten gemeinsamen Teiler von (beliebig vielen) Integern bestimmt.
Dazu habe ich eine Hilfsmethode geschrieben, die prüft ob eine Zahl ein Teiler aller übrigen Zahlen ist. Unten stelle ich ein paar Fragen zu meinem Code. Es ist mir klar, dass es bestimmt schöner geht, aber das ist so eine Möglichkeit, die ich ohne Hilfe aufschreiben konnte.

import java.util.Arrays;

public class ggT {

    public static void main(String[] args) {
        
        System.out.println(determineGGT(10, 7));    /* Einige Tests */
        System.out.println(determineGGT(202, 14, 28));
        System.out.println(determineGGT(40,20,30,220,120,100,1500));
    }

    /**
     * Testet ob
     *
     * @param teiler  Teiler von allen Zahlen in
     * @param numbers ist und gibt
     * @return boolean zurück.
     */
    public static boolean isDivisorOfAll(int teiler, int... numbers) {
        boolean isDivisor = false;
        boolean memory = true;

        for (int number : numbers) {
            if (number % teiler == 0 && memory == true) {
                isDivisor = true;
            }

            else {
                memory = false;
                isDivisor = false;
            }
        }

        return isDivisor;
    }

    /**
     * Bestimmt den größten gemeinsamen Teiler der Zahlen in
     * @param numbers
     * @return ggT
     */
    public static int determineGGT(int... numbers) {
        Arrays.sort(numbers);                            /* Sortiere aufsteigend */
        int minVal = numbers[0];                        /* kleinster Parameterwert; ggT kann höchst diesen Wert annehmen */
        int result = 1;

        for (int teiler = 1; teiler <= minVal; teiler++) {    /* prüfe ob die Zahlen zwischen 1 (inklusive) und minVal (inklusive) */
            if (isDivisorOfAll(teiler, numbers) == true) {      /* Teiler aller Zahlen in numbers sind. */
                result = teiler;
            }
        }
        return result;
    }

}

Fragen:

Zeile 21: Hier definiere ich eine Variable memory, damit ich mir beim Durchlaufen des Arrays irgendwie merken kann, ob teiler ein Teiler eines Array-Eintrags ist. Geht das irgendwie schöner?

Zeile 43-44: Hier sortiere ich zunächst das Array numbers (aufsteigend), damit ich den dann neuen ersten Eintrag als den kleinsten Wert extrahieren kann (denn so groß kann der ggT ja maximal sein). Gibt es einen direkten Weg um den kleinsten Wert in einem Array zu erhalten? Ich habe nichts finden können.

 

[mihe7]

Zeile 21: Hier definiere ich eine Variable memory, damit ich mir beim Durchlaufen des Arrays irgendwie merken kann, ob teiler ein Teiler eines Array-Eintrags ist. Geht das irgendwie schöner?

Es empfiehlt sich grundsätzlich zu überlegen, wie man das per Stift und Papier ermitteln würde. Du möchtest wissen, ob eine Zahl Teiler vieler anderer Zahlen ist. Wenn Du die vielen anderen Zahlen auf einen Block schreibst und der Reihe nach auf Teilbarkeit prüfst, wann kannst Du sicher sein, dass die gegebene Zahl
a) ein Teiler ist
b) kein Teiler ist
?

Zeile 43-44: Hier sortiere ich zunächst das Array numbers (aufsteigend), damit ich den dann neuen ersten Eintrag als den kleinsten Wert extrahieren kann (denn so groß kann der ggT ja maximal sein). Gibt es einen direkten Weg um den kleinsten Wert in einem Array zu erhalten? Ich habe nichts finden können.

Jein.

a) es ist nicht notwendig, zu sortieren

private int min(int ... numbers) {
    int minSoFar = numbers[0];
    for (int number : numbers) {
        if (number < minSoFar) {
            minSoFar = number;
        }
    }
    return minSoFar;
}

b) es gibt die Möglichkeit, mit Streams zu arbeiten:

int min = IntStream.of(numbers).min().getAsInt();

 

[KonradN]

Ein Gedanke, der mir kommt:

ggT von zwei Zahlen ist ja sehr effektiv ermittelbar über den euklidischen Algorithmus.
Ist es nicht deutlich einfacher zu berechnen über diesen Ansatz:

ggT von einer Zahl: die Zahl.
ggT von zwei Zahlen: ggt(zahl1, zahl2) mit ggT dem euklidischen Algorithmus.
ggT von drei Zahlen ist auch ausdrückbar mit ggT(a,b,c) = ggT(a, ggT(b,c))

Das kann man dann problemlos ausdrücken:

public static int ggT(int a, int b) {
    while(b != 0) {
        int c = a;
        a = b;
        b = c % b;
    }
    return a;
}

public static int determineGGT(int... numbers) {
    if (numbers.length == 0) throw IllegalArgumentException("No number given!");
    
    int ggt = numbers[0];
    for (int index = 1; index < numbers.length; index++) {
        ggt = ggT(ggt, numbers[i]);
    }
    return ggt;
}

(Die ggT Implementation habe ich einfach schnell geklaut von https://gist.github.com/heckenmann/978a643c8437a9ffaffc
aber was mich wundert: Ich bin mehrere Treffer durchgegangen - die ersten Treffer haben alle a,b, n,m oder so als Variablen genommen. Ich bin ja vom Glauben abgefallen ... )

 

[KonradN]

Zu Zeile 21 - du versuchst Dich an das EVA Prinzip zu halten, also nur ein Return am Ende? Das führt zu genau so schlecht lesbaren Code und in bevorzuge daher ein Return aus der Menge heraus.

Aber schauen wir uns Deinen Code einfach einmal im Detail an:

    public static boolean isDivisorOfAll(int teiler, int... numbers) {
        boolean isDivisor = false;
        boolean memory = true;

        for (int number : numbers) {
            if (number % teiler == 0 && memory == true) {
                isDivisor = true;
            }

            else {
                memory = false;
                isDivisor = false;
            }
        }

        return isDivisor;
    }

Du gehst die Zahlen durch bis Du eine Zahl findest, die nicht teilbar ist, dann weisst Du, dass das Ergebnis falsch ist und Du kannst abbrechen.

Also erster Rename: "memory" wäre etwas wie "canAbort" oder so.

Dann ist die Variable bereits ein boolean. Es muss also nicht mehr mit == true verglichen werden. Das würde dann daraus machen:
if (number % teiler == 0 && memory) {
(bzw. mit dem ersten rename halt ein canAbort statt memory).

Dann ist Diene Logik ja: So lange, wie die Zahlen teilbar sind, ist das Ergebnis true. Damit kann man das Ergebnis am Anfang auf true setzen und dann kann man das als "default" ansehen:

    public static boolean isDivisorOfAll(int teiler, int... numbers) {
        boolean isDivisor = true;
        boolean memory = true;

        for (int number : numbers) {
            if (number % teiler == 0 && canAbort) {
            } else {
                memory = false;
                isDivisor = false;
            }
        }

        return isDivisor;
    }

Da das if leer ist, kann man die Bedingung umdrehen. !(a && b) = !a || !b und damit hat man dann:

    public static boolean isDivisorOfAll(int teiler, int... numbers) {
        boolean isDivisor = true;
        boolean memory = true;

        for (int number : numbers) {
            if (number % teiler != 0 || !canAbort) {
                memory = false;
                isDivisor = false;
            }
        }

        return isDivisor;
    }

Nun das mit den mehreren return Statements. Man braucht dann das canAbort nicht mehr und auch das Ergebnis muss man sich nicht mehr merken:

    public static boolean isDivisorOfAll(int teiler, int... numbers) {
        for (int number : numbers) {
            if (number % teiler != 0 || !canAbort) {
                return false;
            }
        }

        return true;
    }

Das wäre dann eine Methode, wie ich diese prinzipiell schreiben würde.

Oder als Stream wäre das dann etwas wie:

    public static boolean isDivisorOfAll(final int teiler, int... numbers) {
        return Arrays.stream(numbers) // IntStream
            .filter(n -> n % teiler != 0)    // Nur Elemente, die kein Teiler sind
            .findAny()                // Gibt ein OptionalInt mit ggf einem Element, das nicht teilbar ist
            .isEmpty();               // Optional leer -> Gab keine Zahl, die kein Teiler ist.
    }

 

[mihe7]

Dieser @KonradN nimmt einem alles vorweg

 

[KonradN]

Dieser @KonradN nimmt einem alles vorweg

Irgendwie muss man Dich ja ärgern

 

[httpdigest]

Oder als Stream wäre das dann etwas wie:

    public static boolean isDivisorOfAll(final int teiler, int... numbers) {
        return Arrays.stream(numbers) // IntStream
            .filter(n -> n % teiler != 0)    // Nur Elemente, die kein Teiler sind
            .findAny()                // Gibt ein OptionalInt mit ggf einem Element, das nicht teilbar ist
            .isEmpty();               // Optional leer -> Gab keine Zahl, die kein Teiler ist.
    }

Oder:

public static boolean isDivisorOfAll(final int teiler, int... numbers) {
  return Arrays.stream(numbers) // IntStream
               .allMatch(n -> n % teiler == 0);
}