({{Číslo projektu, CZ.1.07/1.1.36/02.0066}, {Autor, Ladislav Kašpárek}, {Předmět, Programování a vývoj aplikací}, {Téma, Nějvětší společný dělitel}, {Metodický pokyn, výkladový text s ukázkami}})

Největší společný dělitel

Problém

Vstup:	Máte zadána dvě (obecně však N) kladná celá čísla.
Úkol:	Máte najít algoritmus, který spočítá nějvětší společný dělitel těchto dvou čísel.

Co je to největší společný dělitel?

Největší společný dělitel dvou čísel je nejvyšší přirozené číslo, které je obě vydělí beze zbytku.

GCD[112,168]

Hrubá síla

Základní myšlenka:

Vezmu to nižší ze zadaných čísel a postupně jím zkouším obě čísla vydělit. Pokud je dělí obě, tak pak je to největší společný dělitel, pokud ne, pak to číslo snižím o jedna a testuji znovu. V nehorším případě (čísla jsou nesoudělná) se výpočet zastaví na čísle jedna.

Kód:

public static int BruteForce(int u, int v) {
    int pom = 0;
    if (u > v) {
        pom = v;
    } else {
        pom = u;
    }
    while (pom > 1) {
        if (((u % pom) == 0) && ((v % pom) == 0)) {
            return pom;
        }
        pom--;
    }
    return 1;
 }

Pomocí rozkladu na prvočinitele

Základní myšlenka :

Rozložím čísla na součin prvočinitelů a ty mocniny, které mají obě čísla společné, tak tvoří největšího společného dělitele.

Ukázka:

FactorInteger[112]

FactorInteger[168]

Jak je vidět společná mocnina je (2^3)*(7^1), tedy 56.

Pomocí nejmenšího společného násobku

Základní myšlenka :

Pokud máme, nebo jsme spočítali nejmenší společný násobek, tak stačí dosadit do vzorečku:
gcd(a, b)=((a*b)/(lcm(a,b)))

Ukázka:

((112*168)/(LCM[112,168]))

Pomocí Euklidova algoritmu

Tento algoritmus byl vymyšlen někdy 300 let před naším letopočtem. Je hodně jednoduchý ale velmi účinný. Pomocí rozkladu prvočísel se dá určit NSD menších čísel, ale u větších čísel bychom narazili na velký výpočetní čas. Pomocí Euklidova algoritmu dosáhneme rychlejšího výsledku.

Kód:

public static int Eukleid(int u, int v) {
    if (v > u) {
        int pom = u;
        u = v;
        v = pom;
    }
    while (v != 0) {
        int r = u % v;
        u = v;
        v = r;
    }
    return u;
}

Příklady

Spočítejte pomocí hrubé síly největší společný dělitel čísel 13 a 27
Spočítejte pomocí rozkladu na prvočinitele největší společný dělitel čísel 15, 30 a 45
Spočítejte pomocí Euklidova algoritmu největší společný dělitel čísel 1539 a 1328

Zdroje

http://reference.wolfram.com/mathematica/ref/GCD.html
http://reference.wolfram.com/mathematica/ref/FactorInteger.html
http://reference.wolfram.com/mathematica/ref/LCM.html