26 Học Python – Đếm số ước của số nguyên n mới nhất

Bài 26: Kiểm Tra Số Nguyên n Có Phải Là Số Nguyên Tố Bằng Python

Giới Thiệu

Số nguyên tố là một số nguyên dương lớn hơn 1 và chỉ có đúng hai ước là 1 và chính nó. Bài toán kiểm tra số nguyên tố rất quan trọng trong lập trình và có nhiều ứng dụng trong mật mã, thuật toán tối ưu và lý thuyết số. Bài viết này sẽ hướng dẫn cách kiểm tra số nguyên tố bằng Python một cách tối ưu.

Cách Xác Định Số Nguyên Tố

Một số nguyên n được coi là số nguyên tố nếu thỏa mãn các điều kiện sau:

• n lớn hơn 1.
• n chỉ có hai ước là 1 và chính nó.

Viết Chương Trình Python

Chương trình dưới đây kiểm tra một số nguyên n có phải là số nguyên tố hay không.

# Nhập số nguyên từ người dùng

n = int(input(“Nhập số nguyên n: “))

if la_so_nguyen_to(n):

print(f”{n} là số nguyên tố.”)

else:

print(f”{n} không phải là số nguyên tố.”)

Giải Thích Chương Trình

• Kiểm tra n < 2: Nếu n nhỏ hơn 2, không phải số nguyên tố.
• Duyệt từ 2 đến n-1: Kiểm tra nếu n chia hết cho bất kỳ số nào trong khoảng này, thì không phải số nguyên tố.
• Trả về kết quả: Nếu không tìm thấy ước nào ngoài 1 và n, số đó là số nguyên tố.

Tối Ưu Chương Trình

Cách trên có độ phức tạp O(n), có thể được tối ưu thành O(√n) bằng cách chỉ duyệt đến √n:

# Hàm tối ưu kiểm tra số nguyên tố

def la_so_nguyen_to_toi_uu(n):

    if n < 2:

        return False

    if n in (2, 3):

        return True

    if n % 2 == 0 or n % 3 == 0:

        return False

    i = 5

    while i * i <= n:

        if n % i == 0 or n % (i + 2) == 0:

            return False

        i += 6

    return True

# Nhập số nguyên từ người dùng

n = int(input("Nhập số nguyên n: "))

if la_so_nguyen_to_toi_uu(n):

    print(f"{n} là số nguyên tố.")

else:

    print(f"{n} không phải là số nguyên tố.")

Giải Thích Tối Ưu

• Bỏ qua số chẵn và số chia hết cho 3: Giúp loại trừ nhanh các trường hợp không phải số nguyên tố.
• Chỉ kiểm tra đến √n: Vì nếu n có ước lớn hơn √n, thì nó sẽ có ước nhỏ hơn √n.
• Sử dụng bước nhảy 6: Vì số nguyên tố lớn hơn 3 đều có dạng 6k ± 1, ta chỉ cần kiểm tra các số có dạng này.

Ứng Dụng

• Kiểm tra tính nguyên tố của số trong mật mã học.
• Ứng dụng trong thuật toán sàng lọc số nguyên tố.
• Xây dựng thuật toán tối ưu hóa cho các bài toán về số học.

Kết Luận

Bài toán kiểm tra số nguyên tố có thể được giải quyết dễ dàng bằng Python. Sử dụng thuật toán tối ưu giúp giảm thời gian xử lý đáng kể, đặc biệt với các số lớn.