NWD z definicji: szukamy wspólnych dzielników

Algorytm Euklidesa: największy wspólny dzielnik - Informatyka - klasa 8 (Python)

**Największy wspólny dzielnik** (NWD) dwóch liczb to największa liczba, przez którą obie dzielą się bez reszty. NWD(12, 18) = 6, bo 6 dzieli 12 i 18, a większa liczba już nie. Najprostszy sposób: sprawdzić po kolei wszystkie liczby od 1 do mniejszej z dwóch i zapamiętać ostatnią, która dzieli obie. Działa, ale dla dużych liczb robi bardzo dużo kroków. Pod programem licznik `steps` pokazuje, ile.

def gcd_slow(a, b):
    result = 1
    steps = 0
    for d in range(1, min(a, b) + 1):
        steps += 1
        if a % d == 0 and b % d == 0:
            result = d
    print(f"NWD({a}, {b}) = {result}, kroków: {steps}")
    return result

gcd_slow(12, 18)
gcd_slow(84, 36)
gcd_slow(1071, 462)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Informatyka - klasa 8·Zaloguj się, aby zapisać postęp na koncie.