Kiểm tra số nguyên tố trong Python
29 có phải số nguyên tố không? Chỉ cần thử các ước tới căn bậc hai là có đáp án nhanh chóng.
- Định nghĩa số nguyên tố
- Duyệt các ước có thể có
- Dừng khi divisor * divisor > number
Chỉ cần thử đến √n
Vấn đề
Số nguyên tố đứng sau việc mã hóa dữ liệu trên internet, bảng băm (hash table) và rất nhiều câu đố. Kiểm tra một số có nguyên tố không bằng cách thử mọi ước tới chính nó vẫn đúng với 29, nhưng chậm khủng khiếp với số lớn. Một nhận xét nhỏ giúp phép kiểm tra nhanh hơn rất nhiều.
Hình dung đời thường
Tìm ước số giống việc thử xếp gạch thành một hình chữ nhật kín. 36 viên xếp được thành 1×36, 2×18, 3×12, 4×9 và 6×6. Qua hình vuông (6×6), các hình chữ nhật cũ chỉ lặp lại theo chiều xoay ngang, nên không còn gì mới để tìm sau căn bậc hai. Còn 29 viên chỉ xếp được thành 1×29, nên 29 là số nguyên tố.
number > 1🚪 Chỉ số lớn hơn 1 mới có thể là số nguyên tốdivisor * divisor <= number🪞 Dừng ở hình vuông: sau đó chỉ là lặp lạinumber % divisor == 0🔍 Xếp được hình chữ nhật kín: không phải số nguyên tốdivisor += 1➡️ Thử chiều rộng tiếp theoSố nguyên tố là số nguyên lớn hơn 1 chỉ có đúng hai ước dương là 1 và chính nó.
Những điểm quan trọng
is_prime = number > 1bắt đầu bằng False với 0, 1 và số âm, vì chúng không bao giờ là số nguyên tố.while divisor * divisor <= number and is_prime:dừng ở căn bậc hai hoặc ngay khi tìm ra một ước.number % divisor == 0nghĩa làdivisorchia hết số đó.- Với 29, vòng lặp chỉ thử 2, 3, 4 và 5 là đã kết luận được nó là số nguyên tố.
Khi nào nên sử dụng?
- Các câu đố về số như liệt kê số nguyên tố hay phân tích thừa số nguyên tố.
- Hiểu vì sao dừng sớm và chỉ xét tới một giới hạn làm vòng lặp nhanh hơn.
- Kiểm tra dữ liệu nhập trong các công cụ toán học.
Khi nào chưa cần
- Liệt kê mọi số nguyên tố tới một giới hạn lớn: sàng Eratosthenes nhanh hơn nhiều so với kiểm tra từng số.
- Mật mã học với những số dài hàng trăm chữ số: hệ thống thật dùng các phép kiểm tra xác suất.
Code ví dụ
number = 29
is_prime = number > 1
divisor = 2
while divisor * divisor <= number and is_prime:
if number % divisor == 0:
is_prime = False
divisor += 1
print(f"{number} is prime: {is_prime}")
Kết quả khi chạy
29 is prime: True
Giải thích code
Vòng lặp chỉ cần thử các ước số trong khi divisor * divisor <= number. Lý do là nếu n có một ước lớn hơn căn bậc hai của n, thì nó phải đi kèm với một ước nhỏ hơn mà vòng lặp đã kiểm tra trước đó. Nhờ vậy độ phức tạp chỉ còn O(√n), và kết quả cho thấy 29 là số nguyên tố.
Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.
Bài tập mở rộng
Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.
- Thay đổi dữ liệu đầu vào và đoán trước kết quả rồi mới chạy để kiểm tra.
- Thêm phần kiểm tra cho trường hợp dữ liệu rỗng hoặc không hợp lệ.
- Đưa phần xử lý vào một hàm riêng và thử với nhiều bộ dữ liệu khác nhau.
Lỗi hay gặp
Coi 1 là số nguyên tố
1 chỉ có một ước nên không phải số nguyên tố. Hãy kiểm tra number > 1 trước.
is_prime = True # 1 would be reported as prime
is_prime = number > 1
Lặp tới tận chính con số đó
Kết quả vẫn đúng nhưng phải thử nhiều ước hơn mức cần rất nhiều.
for divisor in range(2, number):
while divisor * divisor <= number:
Bạn học xong bài này chưa?
Đánh dấu đã học để theo dõi tiến độ của bạn.
Luyện tập với thử thách
Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.
- Kiểm Tra Số Nguyên Tố Xác định xem một số có phải là số nguyên tố hay không. Dễ
- Ước Số Nguyên Tố Lớn Nhất Tìm số nguyên tố lớn nhất chia hết cho một số nguyên dương. Trung bình
- List Primes With a Sieve Find primes up to a limit by marking composite multiples. Trung bình