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ề:
- Bài 21: Tìm Những Số Chia Hết Cho 3 bằng Python mới nhất
- Bài 22: Đếm Số Lượng Số Chia Hết Cho 3 Bằng Python
- Bài 23 : Tính Tổng Những Số Chẵn Bằng Python
- Bài 24 Tính Tổng Những Số Chia Hết Cho 3 Hoặc 5 Bằng Python
- Bài 25: Đếm Số Ước Của Số Nguyên n Bằng Python
- Bài 26 – Tính Tổng Những Số Chia Hết Cho 3 và 5 bằng Python
- Bài 28: Tính Tổng Các Số Nguyên Từ m Đến n Bằng Python
- Bài 29: Đếm Số Chia Hết Cho 3 Từ m Đến n Bằng Python
- 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đếnn-1, nếu tìm thấy số nào mànchia hết, trả vềFalse. - Nếu không tìm thấy số nào chia hết,
nlà 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
nnhỏ hơn 2, không phải số nguyên tố. - Nếu
nlà 2 hoặc 3, chắc chắn là số nguyên tố. - Nếu
nchia 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
| Phương pháp | Cách hoạt động | Độ phức tạp |
|---|---|---|
| Vòng lặp đơn giản | Kiểm tra từ 2 đến n-1 | O(n) |
| Căn bậc hai (Tối ưu) | Kiểm tra từ 2 đến √n (loại bỏ số chẵn) | O(√n) |
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
