NWD - największy wspólny dzielnik (ang. GCD - Greatest Common Divisor) liczb a i b jest największą liczbą naturalną, która jednocześnie dzieli a i b bez reszty.
Euklides zauważył, że NWD liczb a i b dzieli również ich różnicę.
Schemat blokowy
C++
#include <iostream>
#include <cmath>
using namespace std;
int main(int argc, char ** argv)
{
int a, b, c;
cin >> a;
cin >> b;
if (a != b)
{
while (a%b != 0)
{
c = a;
a = b;
b = c % b;
}
cout << b << endl;
}
else
cout << a << endl;
}
Rozwiązanie w Excel
W komórkach F4 i F5 wpisujemy dowolne liczby „a” i „b”
W komórki arkusza wpisano formuły:
A3=F4 ;
B3=F5 ;
C3=JEŻELI(B3=0;A3;"")
A4=JEŻELI(ORAZ(B3>0;B3<>"");B3;"") - kopiujemy wprowadzoną formułę do wiersza np. 300
B4=JEŻELI(ORAZ(B4>0;B4<>"");MOD(A4;B4);"") - kopiujemy wprowadzoną formułę do wiersza np. 300
Jeżeli w kolumnie „C” pojawi się liczba to jest ona NWD naszych liczb „a” i „b”
Opracował: Eliasz M.
