Program Python untuk Menemukan HCF atau GCD

Faktor persekutuan tertinggi (H.C.F) atau pembagi persekutuan terbesar (G.C.D) dari dua bilangan adalah bilangan bulat positif terbesar yang membagi sempurna dua bilangan yang diberikan. Misalnya, H.C.F dari 12 dan 14 adalah 2.

Kode Sumber: Menggunakan Loops

# Python program to find H.C.F of two numbers

# define a function
def compute_hcf(x, y):

# choose the smaller number
    if x > y:
        smaller = y
    else:
        smaller = x
    for i in range(1, smaller+1):
        if((x % i == 0) and (y % i == 0)):
            hcf = i 
    return hcf

num1 = 54 
num2 = 24

print("The H.C.F. is", compute_hcf(num1, num2))

Keluaran

The H.C.F. is 6

Di sini, dua bilangan bulat disimpan dalam variabel num1 dan num2 diteruskan ke compute_hcf() fungsi. Fungsi ini menghitung H.C.F. dua angka ini dan mengembalikannya.

Dalam fungsinya, pertama-tama kita menentukan bilangan yang lebih kecil dari kedua bilangan tersebut karena H.C.F hanya boleh kurang dari atau sama dengan bilangan terkecil. Kami kemudian menggunakan file for putaran untuk beralih dari 1 ke nomor itu.

Di setiap iterasi, kami memeriksa apakah bilangan kami membagi dengan sempurna kedua bilangan input. Jika demikian, kami menyimpan nomor tersebut sebagai H.C.F. Setelah menyelesaikan perulangan, kita berakhir dengan angka terbesar yang membagi kedua angka dengan sempurna.

Metode di atas mudah dipahami dan diterapkan tetapi tidak efisien. Metode yang jauh lebih efisien untuk menemukan H.C.F. adalah algoritma Euclidean.

Algoritma euclidean

Algoritma ini didasarkan pada fakta bahwa H.C.F. dari dua angka membagi perbedaan mereka juga.

Dalam algoritma ini, kita membagi yang lebih besar dengan yang lebih kecil dan mengambil sisanya. Sekarang, bagi yang lebih kecil dengan sisa ini. Ulangi sampai sisanya 0.

Misalnya, jika kita ingin mencari H.C.F. dari 54 dan 24, kita bagi 54 dengan 24. Sisanya adalah 6. Sekarang, kita membagi 24 dengan 6 dan sisanya 0. Oleh karena itu, 6 adalah H.C.F.

Kode Sumber: Menggunakan Algoritma Euclidean

# Function to find HCF the Using Euclidian algorithm
def compute_hcf(x, y):
   while(y):
       x, y = y, x % y
   return x

hcf = compute_hcf(300, 400)
print("The HCF is", hcf)

Di sini kita mengulang sampai y menjadi nol. Pernyataan x, y = y, x % y melakukan pertukaran nilai dengan Python. Klik di sini untuk mempelajari lebih lanjut tentang menukar variabel dengan Python.

Di setiap iterasi, kami menempatkan nilai y di x dan sisanya (x % y) di y, secara bersamaan. Kapan y menjadi nol, kami memiliki H.C.F. di x.