Liczby względnie pierwsze

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

Leave a Reply

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>