Liczby względnie pierwsze

Wyjaśnienie problemu

Jeżeli dwie liczby całkowite a i b spełniają warunek NWD(a,b)=1, czyli nie mają żadnego naturalnego dzielnika oprócz 1, to liczby takie nazywamy liczbami względnie pierwszymi. Rozkłady na czynniki pierwsze liczb względnie pierwszych wyróżniają się brakiem czynników wspólnych dla wszystkich liczb.

Zatem

jeśli rozkładamy dwie  liczby na czynniki pierwsze to liczby po prawej stronie tabeli z pierwszej liczby nie powtórzą się w liczbach znajdujących się po prawej stronie rozkładu drugiej liczby.

Przykład

15=3⋅5
28=2⋅2⋅7
wspólne czynniki: brak
nwd(15,28)=1
Liczby 15 i 28 są względnie pierwsze.

15=3⋅5
16=2⋅2⋅2⋅2
wspólne czynniki: brak
nwd(15,16)=1
Liczby 15 i 16 są względnie pierwsze.

25=5⋅5
27=3⋅3⋅3
wspólne czynniki: brak
nwd(25,27)=1
Liczby 25 i 27 są względnie pierwsze.

Algorytm

Dane wejściowe

Dane wyjściowe