Autorzy:Joanna Czarnowska, Jolanta Wesołowska, Wojciech Babiański, Lech Chańko
Wydawnictwo:Nowa Era
Rok wydania:2014
Sformułuj algorytm wyznaczania największego wspólnego dzielnika 4.2 gwiazdek na podstawie 5 opinii

Sformułuj algorytm wyznaczania największego wspólnego dzielnika

11Zadanie
12Zadanie
13Zadanie
14Zadanie
15Zadanie
16Zadanie
17Zadanie
18Zadanie
19Zadanie
20Zadanie

`ul(ul("algorytm wyznaczania NWD trzech liczb"))` 

1. Wyznaczamy NWD dwóch liczb, na przykład NWD(x,y) i oznaczamy je jako w. 

2. Wyznaczamy NWD pozostałej liczby i w (NWD(z, w)). 

 

W każdym przykładzie mamy już zapisane liczby w postaci rozkłądu na czynniki pierwsze. 

Aby znaleźć NWD bierzemy tylko te czynniki pierwsze, które pojawiają się w rozkładzie obu liczb - jeśli w obu liczbach występuje ten sam czynnik pierwszy, ale w różnych potęgach, to bierzemy mniejszą potęgę. Jeśli czynnik występuje tylko w jednej liczbie, to nie bierzemy go do iloczynu. 

`a)` 

Zgodnie z algorytmem najpierw wyznaczamy NWD dwóch pierwych liczb:

`NWD(x,\ y)=2*3*5=30` 

NWD(x, y) oznaczamy jako w:

`w=2*3*5` 

Wyznaczamy NWD danych trzech liczb, czyli NWD ostatniej liczby i liczby w:

`NWD(x,\ y,\ z)=NWD(z,\ w)=2*3=6` 

 

 

 

`b)` 

Wyznaczamy NWD(x,y). Zauważmy, że nie ma sensu wymnażać, ponieważ dalej będziemy szukać NWD(z, w)

`NWD(x,\ y)=2^2*3^2*5*7^2`  

`w=2^2*3^2*5*7^2` 

`NWD(x,\ y,\ z)=NWD(z,\ w)=2*3^2*5*7=2*9*5*7=630`