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

.