JS – gcd brute force

Piszemy program, który znajduje najwyższy wspólny dzielnik dwóch liczb. Na razie metoda brute force, lepsze podejście w następnej lekcji.

Ok, pomyślmy – mamy 2 liczby. Jaki będzie najwyższy wspólny dzielnik?

Cóż, na pewno nie będzie większy od mniejszej liczby. Czyli jak mamy 6 i 16 to na pewno nie będzie większy niż 6 (mniejsza liczba).

Ok, a czy może być równy mniejszej liczbie?

Może. Np. 2 i 4 (2). Albo 5 i 125.

Krótko mówiąc bierzemy minimum z obu liczb i sprawdzamy czy liczba x i y jest podzielna przez tę mniejszą. Jak nie to zmniejszamy.

Koniec końców któraś będzie dzielnikiem a jak nie to będą chociaż podzielne przez 1.

Oto kod:

function gcdBruteForce(x, y){

    let smallerOne = Math.min(x, y);

    while(smallerOne > 1){
        if(x % smallerOne === 0 && y % smallerOne === 0)
            return smallerOne;

        smallerOne--;
    }

    return 1;
}

console.log(gcdBruteForce(5,125)); //5
console.log(gcdBruteForce(25,125)); //25
console.log(gcdBruteForce(6,16)); //2
console.log(gcdBruteForce(8, 30)); //2

Zawsze bierze tę mniejszą i sprawdza, czy obie są podzielne przez nią. Jak nie to zmniejsza o 1 i dalej sprawdza, aż znajdzie. Jak nie znajdzie to obie i tak są przez 1 podzielne.