Algorytm Euklidesa w Pythonie

powrót

Zasada działania algorytmu została opisana w tym miejscu.

Poniżej znajduje się program, który wyznacza największy wspólny dzielnik wersja nieoptymalna.

# --------algorytm.edu.pl----------
# algorytm Euklidesa, wersja nieoptymalna
def nwd(a, b):
    while a!= b:
        if a > b:
            a -= b
        else:
            b -= a
    return a

# główna część programu
a = int(input("Podaj pierwszą liczbę: "))
b = int(input("Podaj drugą liczbę: "))
print(f"Największy wspólny dzielnik liczb {a} i {b} wynosi",nwd(a, b))

Poniżej znajduje się program, który wyznacza największy wspólny dzielnik wersja optymalna.

# --------algorytm.edu.pl----------
# algorytm Euklidesa, wersja optymalna
def nwd(a, b):
    while b > 0:
        pom = a
        a = b
        b = pom % b
    return a

# główna część programu
a = int(input("Podaj pierwszą liczbę: "))
b = int(input("Podaj drugą liczbę: "))
print(f"Największy wspólny dzielnik liczb {a} i {b} wynosi",nwd(a, b))

Przykładowe wejście/wyjście

Podaj pierwszą liczbę: 25
Podaj drugą liczbę: 105
Największy wspólny dzielnik liczb 25 i 105 wynosi 5

Wersja rekurencyjna algorytmu Euklidesa, wersja optymalna.

# --------algorytm.edu.pl----------
# algorytm Euklidesa, wersja optymalna
def nwd(a, b):
    if b > 0:
        return nwd(b, a % b)
    return a

# główna część programu
a = int(input("Podaj pierwszą liczbę: "))
b = int(input("Podaj drugą liczbę: "))
print(f"Największy wspólny dzielnik liczb {a} i {b} wynosi",nwd(a, b))

W części praktycznej arkusza maturalnego, w razie potrzeby możesz użyć gotowego rozwiązania gcd.