Najwyższy wspólny współczynnik Pythona (HCF / GCD)

Oblicz najwyższy wspólny współczynnik (HCF) lub największy wspólny dzielnik (GCD) dwóch liczb, korzystając z algorytmu Euklidesa.

Spróbuj w Edytorze

Przegląd

Najwyższy wspólny współczynnik (HCF), znany również jako największy wspólny dzielnik (GCD), to największa dodatnia liczba całkowita, która dzieli dwie lub więcej liczb całkowitych bez pozostawiania reszty.

Algorytm Euklidesa jest niezwykle wydajną metodą obliczania HCF. Stwierdza, że NWD dwóch liczb również dzieli ich różnicę.

W Pythonie implementujemy to iteracyjnie, używając pętli while, w której w sposób ciągły zastępujemy większą liczbę resztą ich podziału.

Dane wyjściowe kodu i wykonania

Implementacja pętli euklidesowej w celu znalezienia HCF/GCD dwóch liczb.

hcf_gcd.py

Spróbuj w Edytorze

def find_gcd(a, b):
    # Euclidean Algorithm
    while b != 0:
        a, b = b, a % b
    return a

print("GCD of 36 and 60 is:", find_gcd(36, 60))
print("GCD of 17 and 5 is: ", find_gcd(17, 5))

Wyjście terminala

GCD of 36 and 60 is: 12
GCD of 17 and 5 is:  1

Wdrażanie krok po kroku

Uproszczenie ułamków i silniki matematyczne
Algorytmy kryptograficzne (takie jak generowanie kluczy prywatnych RSA)
Projektowanie cyklicznych harmonogramów wydarzeń

Często zadawane pytania

Czy Python ma wbudowaną funkcję GCD?

Tak! Standardowa biblioteka Pythona zawiera plik `math.gcd(a, b)`, który pod maską wykorzystuje skompilowaną implementację C.

Powiązane tematy

Najniższa wspólna wielokrotność Pythona (LCM)

Znajdź najniższą wspólną wielokrotność (LCM) dwóch liczb, korzystając z ich relacji HCF w Pythonie.

Prosty skrypt kalkulatora w Pythonie

Zbuduj prosty kalkulator w Pythonie. Dowiedz się, jak mapować operatory matematyczne, wykonywać przepływy wykonywania przez użytkowników i natywnie obsługiwać logikę.