27 Học Python – Kiểm tra số nguyên tố bằng Python (2 cách tối ưu)

Bài 27: Kiểm tra số nguyên tố bằng Python (2 cách tối ưu)

Giới thiệu

Số nguyên tố là số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Trong bài viết này, chúng ta sẽ viết chương trình kiểm tra số nguyên tố bằng hai cách: cách đơn giản và cách tối ưu hơn.

Ưu Đãi lớn thêm danh sách 10 bài tập python  rèn luyện kỹ năng và nâng cao tay nghề:

1. Bài 21: Tìm Những Số Chia Hết Cho 3 bằng Python mới nhất
2. Bài 22: Đếm Số Lượng Số Chia Hết Cho 3 Bằng Python
3. Bài 23 : Tính Tổng Những Số Chẵn Bằng Python
4. Bài 24 Tính Tổng Những Số Chia Hết Cho 3 Hoặc 5 Bằng Python
5. Bài 25: Đếm Số Ước Của Số Nguyên n Bằng Python
6. Bài 26 – Tính Tổng Những Số Chia Hết Cho 3 và 5 bằng Python

7. Bài 27: Kiểm tra số nguyên tố bằng Python (2 cách tối ưu)

8. Bài 28: Tính Tổng Các Số Nguyên Từ m Đến n Bằng Python
9. Bài 29: Đếm Số Chia Hết Cho 3 Từ m Đến n Bằng Python
10. Bài 30 Đếm Số Chia Hết Cho 3 Hoặc 5 Và Tính Tổng Các Số Chẵn Bằng Python

Cách 1: Kiểm tra số nguyên tố bằng vòng lặp đơn giản

Phương pháp này kiểm tra xem số đó có chia hết cho bất kỳ số nào từ 2 đến n-1 hay không.

Chương trình:

# Hàm kiểm tra số nguyên tố (cách đơn giản)
def la_so_nguyen_to(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True
# Kiểm tra
n = int(input("Nhập số cần kiểm tra: "))
print(f"{n} là số nguyên tố" if la_so_nguyen_to(n) else f"{n} không phải là số nguyên tố")

Giải thích:

• Nếu n < 2, kết quả trả về False (không phải số nguyên tố).
• Duyệt từ 2 đến n-1, nếu tìm thấy số nào mà n chia hết, trả về False.
• Nếu không tìm thấy số nào chia hết, n là số nguyên tố (True).

⏳ Độ phức tạp: O(n) (Chạy chậm nếu n lớn). ⏳

Cách 2: Kiểm tra số nguyên tố bằng căn bậc hai (Tối ưu)

Thay vì kiểm tra từ 2 đến n-1, ta chỉ cần kiểm tra từ 2 đến √n. Nếu n có ước số khác 1 và n, nó chắc chắn nằm trong đoạn 2 → √n.

Chương trình:

import math

# Hàm kiểm tra số nguyên tố (cách tối ưu)
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
    for i in range(5, int(math.sqrt(n)) + 1, 2):  # Chỉ kiểm tra số lẻ từ 5 trở đi
        if n % i == 0:
            return False
    return True

# Kiểm tra
n = int(input("Nhập số cần kiểm tra: "))
print(f"{n} là số nguyên tố" if la_so_nguyen_to_toi_uu(n) else f"{n} không phải là số nguyên tố")

Giải thích:

• Nếu n nhỏ hơn 2, không phải số nguyên tố.
• Nếu n là 2 hoặc 3, chắc chắn là số nguyên tố.
• Nếu n chia hết cho 2 hoặc 3, nó không phải số nguyên tố.
• Duyệt từ 5 đến √n, kiểm tra các số lẻ (vì số chẵn đã bị loại trước đó).

⏳ Độ phức tạp: O(√n) (Nhanh hơn nhiều so với O(n)).

So sánh hai cách

Cách tối ưu nhanh hơn rất nhiều và nên dùng khi n lớn!

Kết luận

Chúng ta đã tìm hiểu hai cách kiểm tra số nguyên tố trong Python: một cách dễ hiểu và một cách tối ưu hơn. Nếu bạn muốn kiểm tra số lớn, hãy sử dụng phương pháp căn bậc hai để giảm thời gian tính toán.

Bạn thích cách nào hơn? Hãy thử chạy code và trải nghiệm nhé!

Nếu bạn thấy hay ! xin bạn 1 phút ! vui lòng đánh giá 5 sao cho trang website của chúng tôi ! để có động lực làm thêm nhiều bài hay nữa ! cảm ơn quý khách nhé !

Khóa học Python online từ cơ bản đến nâng cao