Еуклидов алгоритам¶
Еуклидов алгоритам је један ефикасан поступак проналажења највећег заједничког делиоца два броја. Тај поступак се заснива на опажању да је сваки заједнички делилац пара бројева a и b уједно и заједнички делилац пара бројева b и a % b и обрнуто (уз претпоставку да b није нула). Због тога парови (a, b) и (b, a % b) имају исти највећи заједнички делилац.
Поступак се сада састоји у томе да пар (a, b) замењујемо паром (b, a % b) док b не постане нула, а тада је a тражени највећи заједнички делилац.
Када умемо ефикасно да одредимо највећи заједнички делилац (NZD), тај поступак можемо да искористимо за одређивање најмањег заједничког садржаоца (NZS). Искористићемо једнакост \(NZD(a, b) \cdot NZS(a, b) = a \cdot b\), коју ћемо прихватити без доказа (покушајте да је докажете сами). Одавде лако добијамо \(NZS(a, b) = {{a \cdot b} \over NZD(a, b)}\). Да бисмо смањили могућност прекорачења опсега целих бројева, боље је да у програму рачунамо \(NZS(a, b) = a \cdot {b \over NZD(a, b)}\) или \(NZS(a, b) = b \cdot {a \over NZD(a, b)}\), то јест да прво извршимо дељење па онда множење.
У наставку можете да нађете задатке на тему NZD и NZS.