Lập trình Python, Tin tức

Các hàm cơ bản tìm ước chung lớn nhất trong Python

CÁC HÀM THƯỜNG SỬ DỤNG TRONG PYTHON

1. Thuật toán tìm ước chung lớn nhất

Thuật toán tìm ước chung lớn nhất (GCD – Greatest Common Divisor) giữa hai số nguyên a và b là một thuật toán phổ biến để tìm ước chung lớn nhất của hai số đó. Có hai phương pháp phổ biến để thực hiện thuật toán GCD: phương pháp Euclid và phương pháp trừ đi.

  1. Phương pháp Euclid:
    • Bước 1: Cho a và b là hai số nguyên dương ban đầu.
    • Bước 2: Thực hiện phép chia chia lấy dư a cho b và gán giá trị dư vào biến tạm temp.
    • Bước 3: Gán giá trị của b cho a và giá trị của temp cho b.
    • Bước 4: Lặp lại các bước 2 và 3 cho đến khi bằng 0.
    • Bước 5: Kết quả cuối cùng là giá trị a, đó chính là ước chung lớn nhất của a và b.

Dưới đây là một ví dụ mã giả Python cho phương pháp Euclid:

def gcd_euclid(a, b):
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a

# Example usage:
a = 24
b = 36
result = gcd_euclid(a, b)
print("GCD of", a, "and", b, "is", result)
Với đầu vào a = 24 và b = 36, đầu ra sẽ là:

GCD of 24 and 36 is 12
  1. Phương pháp trừ đi:
    • Bước 1: Cho a và b là hai số nguyên dương ban đầu.
    • Bước 2: So sánh a và b.
    • Bước 3: Nếu a lớn hơn b, trừ b từ a và gán kết quả vào a.
    • Bước 4: Nếu b lớn hơn a, trừ a từ b và gán kết quả vào b.
    • Bước 5: Lặp lại các bước 2 đến 4 cho đến khi a và b bằng nhau.
    • Bước 6: Kết quả cuối cùng là giá trị a (hoặc b), đó chính là ước chung lớn nhất của a và b.
Dưới đây là một ví dụ mã giả Python cho phương pháp trừ đi:

def gcd_subtraction(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

# Example usage:
a = 24
b = 36
result = gcd_subtraction(a, b)
print("GCD of", a, "and", b, "is", result) Với đầu vào a = 24 và b = 36, đầu ra sẽ là:

GCD of 24 and 36 is 12

2. Kiểm tra xem một số nguyên dương nào đó có phải là số nguyên tố

Để kiểm tra xem một số nguyên dương nào đó có phải là số nguyên tố hay không, ta có thể sử dụng thuật toán kiểm tra số nguyên tố cơ bản như sau:

  1. Kiểm tra các trường hợp đặc biệt:

    • Nếu số đang xét là 2 hoặc 3, trả về True vì 2 và 3 là số nguyên tố.
    • Nếu số đang xét nhỏ hơn 2, trả về False vì không có số nguyên tố nào nhỏ hơn 2.

  2. Kiểm tra chia hết cho các số từ 2 đến căn bậc hai của số đang xét:

    • Duyệt qua các số từ 2 đến căn bậc hai của số đang xét.
    • Nếu số đang xét chia hết cho bất kỳ số nào trong khoảng này, trả về False vì nó không phải là số nguyên tố.
    • Nếu không có số nào chia hết, tiếp tục với bước tiếp theo.

  3. Trả về True:

    • Nếu số đang xét không chia hết cho bất kỳ số nào từ 2 đến căn bậc hai của nó, trả về True vì nó là số nguyên tố.

Dưới đây là một ví dụ mã giả Python cho thuật toán kiểm tra số nguyên tố:

import math
def is_prime(n):
    if n == 2 or n == 3:
        return True
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
# Example usage:
number = 17
is_prime_number = is_prime(number)
print(number, “is prime:”, is_prime_number)

# Example usage:
number = 17
is_prime_number = is_prime(number)
print(number, "is prime:", is_prime_number)

Với đầu vào number = 17, đầu ra sẽ là:

basic

17 is prime: True

Với đầu vào number = 20, đầu ra sẽ là:

basic

20 is prime: False

Thuật toán trên có độ phức tạp thời gian là O(√n), trong đó n là số đang xét.

Để lại một bình luận