Bài 16.7 - Kiểm tra số nguyên tố trong Python
Khóa học Python từ Cơ bản đến Nâng cao
Chương 1: Làm quen với Python + Ôn tập I/O, biến, kiểu dữ liệu
Chương 2: Câu lệnh rẽ nhánh, vòng lặp, hàm
Chương 3: Xử lý chuỗi và danh sách nâng cao
Chương 4: Bài kiểm tra Python cơ bản + sửa bài
Chương 5: Duyệt mảng, tìm max/min, đếm
Chương 6: Thuật toán sắp xếp
Chương 7: Prefix Sum + Two Pointers
Chương 8: Backtracking cơ bản
Chương 9: Ôn tập thuật toán cơ bản + kiểm tra
Chương 10: Dynamic Programming cơ bản
Chương 11: Đệ quy và DP nâng cao
Chương 12: Đồ thị cơ bản – DFS, BFS
Chương 13: Đồ thị nâng cao – Dijkstra + Topo sort
Chương 14: Cây – Tree traversal + LCA
Chương 15: Bitmask – Kỹ thuật đại số
Chương 16: Số học + Modular Arithmetic
Chương 17: Class
Chương 18: File và Exception

Bài 16.7 - Kiểm tra số nguyên tố trong Python
Giới thiệu
Số nguyên tố là một số tự nhiên lớn hơn 1 và chỉ có thể chia hết cho 1 và chính nó. Việc kiểm tra một số có phải là số nguyên tố hay không là một bài toán thú vị và rất phổ biến trong lập trình. Trong bài viết này, bạn sẽ học cách kiểm tra số nguyên tố trong Python bằng cách sử dụng vòng lặp và các điều kiện cơ bản.
Ví dụ 1: Kiểm tra số nguyên tố cơ bản
Đầu tiên, chúng ta sẽ viết một chương trình đơn giản để kiểm tra xem một số có phải là số nguyên tố hay không. Một số là nguyên tố nếu nó không chia hết cho bất kỳ số nào ngoài 1 và chính nó.
def kiem_tra_nguyen_to(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
# Kiểm tra số 29
so = 29
if kiem_tra_nguyen_to(so):
print(f"{so} là số nguyên tố.")
else:
print(f"{so} không phải là số nguyên tố.")
Giải thích:
- Chúng ta định nghĩa một hàm
kiem_tra_nguyen_to(n)
nhận vào một sốn
và kiểm tra nếun
chia hết cho bất kỳ số nào từ 2 đến căn bậc hai củan
. - Nếu có số nào chia hết, ta kết luận
n
không phải là số nguyên tố. - Nếu không có số nào chia hết, thì
n
là số nguyên tố.
Kết quả:
29 là số nguyên tố.
Ví dụ 2: Kiểm tra nhiều số nguyên tố
Để kiểm tra nhiều số, bạn có thể sử dụng vòng lặp để duyệt qua một danh sách các số và kiểm tra từng số một.
def kiem_tra_nguyen_to(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
# Danh sách các số
so_list = [11, 16, 23, 24, 31, 45]
for so in so_list:
if kiem_tra_nguyen_to(so):
print(f"{so} là số nguyên tố.")
else:
print(f"{so} không phải là số nguyên tố.")
Giải thích:
- Chúng ta sử dụng vòng lặp để kiểm tra từng số trong danh sách
so_list
. - Hàm
kiem_tra_nguyen_to
sẽ được gọi cho từng phần tử và in kết quả ra màn hình.
Kết quả:
11 là số nguyên tố.
16 không phải là số nguyên tố.
23 là số nguyên tố.
24 không phải là số nguyên tố.
31 là số nguyên tố.
45 không phải là số nguyên tố.
Ví dụ 3: Kiểm tra số nguyên tố với số lượng lớn
Khi bạn cần kiểm tra một số lớn, phương pháp này vẫn hoạt động tốt. Tuy nhiên, nếu số rất lớn, bạn có thể cần tối ưu hóa thêm. Dưới đây là một ví dụ kiểm tra số nguyên tố với số lớn.
so_lien_tiep = 1000001
if kiem_tra_nguyen_to(so_lien_tiep):
print(f"{so_lien_tiep} là số nguyên tố.")
else:
print(f"{so_lien_tiep} không phải là số nguyên tố.")
Giải thích:
- Trong ví dụ này, chúng ta kiểm tra số
1000001
. Nhờ vào việc giới hạn vòng lặp kiểm tra đến căn bậc hai của số, thuật toán vẫn có thể xử lý các số khá lớn một cách hiệu quả.
Kết quả:
1000001 không phải là số nguyên tố.
Kết luận
Việc kiểm tra số nguyên tố trong Python là một bài toán cơ bản nhưng rất quan trọng trong lập trình. Chúng ta đã học cách sử dụng vòng lặp và toán tử modulo để xác định xem một số có phải là số nguyên tố hay không. Bạn có thể áp dụng các phương pháp này để giải quyết nhiều bài toán khác trong lập trình.
Hy vọng bạn đã nắm vững cách kiểm tra số nguyên tố và có thể áp dụng vào các bài toán tiếp theo!
#HappyCoding cùng FullhouseDev! 🚀
Khóa học liên quan

Comments