Odpowiedź:
a=int(input("Podaj pierwszą liczbę: "))
b=int(input("Podaj drugą liczbę: "))
x=a
y=b
while a!=b:
if a>b:
a=a-b
else:
b=b-a
if a==1:
print('Liczby',x,'i',y,'są względnie pierwsze.')
else:
print('Liczby',x,'i',y,'nie są liczbami względnie pierwszymi.')
Wyjaśnienie:
Dwie liczby są względnie pierwsze jeśli nie mają wspólnych podzielników różny od 1 i -1.
Ujmując to inaczej:
Dwie liczby są względnie pierwsze, gdy ich Największy Wspólny Dzielnik wynosi 1.
Będziemy więc szukać NWD podanych liczb. Zrobimy to za pomocą Algorytmu Euklidesa w wersji z odejmowaniem (odejmujemy od większej liczby mniejszą, a wynik podstawiamy za większą liczbę. Wykonujemy tą operację do momentu, aż obie liczby będą sobie równe. Liczba ta jest wówczas NWD tych liczb.
