Največji skupni delitelj
Iz Wikipedije, proste enciklopedije
Nàjvéčji skúpni delítelj (tudi nàjvéčja skúpna méra) celih števil je v matematiki največji od deliteljev, ki so skupni številoma. Kot funkcijo ga po navadi označujemo z D(n, k). V tuji literaturi ga označujejo z GCD (n, k) ali z gcd (n, k).
Primer:
- število 28 ima delitelje 1, 2, 4, 7, 14, 28
- število 24 ima delitelje 1, 2, 3, 4, 6, 12, 24
- skupni delitelji so 1, 2, 4
- največji skupni delitelj je 4, in zapišemo D(24, 28) = 4.
V najslabšem primeru imata števili samo enega delitelja 1 (D(n, k) = 1) in v tem primeru sta števili tuji.
Obstaja več metod za določanje največjega skupnega delitelja, najbolj znani sta metoda s pomočjo razcepa na praštevila in Evklidov algoritem.
Programsko lahko izračunamo največji skupni delitelj dveh števil z uporabo funkcij MOD in DIV v paskalu
x := 28; // stevilo a y := 24; // stevilo b dmax := 1; for i:=1 to x do begin if ((x mod i) = 0 AND ((y mod i) =0) then dmax:= i; end; writeln(dmax); //izpiše 4
