Największy Wspólny Dzielnik (

NWD

)

Najmniejsza Wspólna Wielokrotność 

(

NWW

)

Zajęcia 12

Wyznaczanie NWD liczb 

a

 i 

b

Zadanie

Napisz program w C++ wyznaczający 

NWD

 liczb 

a

 i 

b

 na dwa sposoby, tj.

1. Stosując algorytm Euklidesa zgodny z następującym schematem blokowym:

2. Rozkładając liczby 

a

 i 

b

 na czynniki pierwsze, a następnie pamiętając, że 

NWD(a,b)

, to iloczyn wszystkich czynników pierwszych, które powtórzyły się w 

obydwu liczbach, z uwzględnieniem krotności ich wystąpienia.

Zmodyfikowany algorytm Euklidesa wyznaczania 

NWD

 

liczb 

a

 i 

b

Zadanie

Napisz program w C++ realizujący powyższy schemat blokowy.

NWW liczb a i b

Zadanie

Napisz program w C++ wyznaczający 

NWW

 liczb 

a

 i 

b

 na dwa sposoby, tj.

1. Stosując zależność:

NWW(a,b)*NWD(a,b)=a*b

2. Rozkładając liczby 

a

 i 

b 

na czynniki pierwsze, a następnie pamiętając, że 

NWW(a,b)

, to iloczyn wszystkich czynników pierwszych z obydwu liczb, które 

choć raz wystąpiły w każdej z nic i uwzględniając ich krotność.

Praca Domowa

Napisz dwa programy w C++ za pomocą których znajdziesz Największy Wspólny 
Dzielnik i Najmniejszą Wspólną Wielokrotność trzech liczb naturalnych 

a

, 

b

 i 

c

.