Số lượt xem: 4.805 Show Toán học trong lập trình là một mảng phổ biến và thú vị nhưng cũng khá phức tạp. Trong các bài học tới đây, chúng ta sẽ đi tìm hiểu về vấn đề này. Mở đầu, chúng ta sẽ cùng nhau đi tìm hiểu về các thuật toán kiểm tra số nguyên tố cũng như một kĩ thuật cho phép đánh dấu nhanh các số nguyên tố. Nội dungĐể có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:
Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:
Phương pháp kiểm tra số nguyên tốKhái niệm số nguyên tốSố nguyên tố là số tự nhiên lớn hơn 1 và không phải là tích của hai số tự nhiên nhỏ hơn. Nói cách khác, số nguyên tố là những số chỉ có 2 ước là 1 và chính nó. Các nguyên số lớn hơn 1 và không phải là số nguyên tố thì là hợp số. Riêng 0 và 1 không phải là số nguyên tố cũng không phải là hợp số. Ví dụ: 2, 3, 5, 11 là các số nguyên tố nhưng 6 không phải là số nguyên tố do 6 có 2 ước là 2 và 3 Cách kiểm tra số nguyên tốThuật toán cơ bảnTừ định nghĩa của số nguyên tố, ta có thể nghĩ đến việc duyệt tất cả các số từ 2 đến. Nếu chia hết cho bất cứ số nào nghĩa là không phải số nguyên tố. ` include<bits/stdc++.h>using namespace std; int n; bool isPrime(int num){ }
int main(){ }
`Ta có thể thấy ngay, độ phức tạp của thuật toán trên là. Vậy thì liệu có thuật toán nào tốt hơn không? Nhận xétTa có một nhận xét sau về số nguyên tố: Nếu như không phải là số nguyên tố thì tồn tại một ước nguyên tố của nhỏ hơn hoặc bằng. Thật vậy, giả sử không phải là số nguyên tố mà các ước của nó đều lớn hơn thì tích của hai ước bất kì sẽ lớn hơn (Vô lí). Thuật toán cải tiếnTừ nhận xét trên, ta thấy chỉ cần duyệt các ước đến √n để kiểm tran có phải số nguyên tố hay không. ` include<bits/stdc++.h>using namespace std; int n; bool isPrime(int num){ }
int main(){ }
`Khi này, độ phức tạp của thuật toán sẽ giảm xuống còn. Trong đoạn code trên, có một chi tiết mà mình muốn các bạn lưu ý về vòngfor. Tại sao điều kiện vòng lặp của mình là thay vì? Lí do là vì nếu như viết thì tại mỗi lần lặp lại của vòngfor, máy tính sẽ phải tính lại giá trị của khiến cho thuật toán chạy chậm hơn không cần thiết. Đây là một kinh nghiệm cho các bạn khi viết code. Ví dụ thay vì viết các bạn có thể viết. Sàng EratosthenesBây giờ, chúng ta có một yêu cầu như sau: Cho một số nguyên dương. Hãy đánh dấu tất cả các số nguyên tố trong phạm vi từ 2 đến. Thuật toán cơ bảnVới những kiến thức về cách kiểm tra số nguyên tố ở trên bên, chúng ta có thể nghĩ đến việc duyệt tất cả các số từ 2 đến và dùng hàm kiểm tra số nguyên tố. ` include<bits/stdc++.h>using namespace std; const int MaxN = 1 + 1e6; int n; bool mark[MaxN]; bool isPrime(int num){ }
int main(){ }
`Tuy nhiên, độ phức tạp của chương trình trên là . Liệu có thuật toán nào cho thời gian tốt hơn không? Phương phápTrên thực tế, đã có một phương pháp lọc các số nguyên tố được đưa ra bởi nhà toán học cổ đại ngườiHy Lạp Eratosthene. Vậy chính xác ông đã làm thế nào? Ông lấy lá cọ, ghi tất cả các số từ 2 đến 100. Ông xét lần lượt từng số. Đầu tiên, gặp số 2 chưa bị chọc thủng, ông sẽ chọc thủng tất cả các số khác 2 trên lá cọ mà chia hết cho 2. Tiếp theo, gặp số 3 chưa bị chọc thủng, ông sẽ chọc thủng tất cả các số khác 3 trên lá cọ mà chia hết cho 3. Lúc này, số 4 đã bị chọc thủng nên ông bỏ qua và tiếp tục đến 5. Sau khi kết thúc, các số còn lại đều là số nguyên tố và lá cọ khi này giống như một cái sàng nên người ta gọi đây là “Sàng Eratosthene”. Tại sao cách làm trên lại có thể loại bỏ tất cả các số nguyên tố? Ta thấy, qua mỗi bước, các số chia hết cho một số nguyên tố nào đó sẽ bị loại bỏ đi như ở bước 1 là các số chia hết cho 2, ở bước 2 là các số chia hết cho 3 nên đến cuối cùng, sẽ chỉ còn sót lại các số chia hết cho chính nó (chính là các số nguyên tố). Thuật toán cải tiếnTừ những thông tin về sàng ở trên, ta có thể đưa ra chương trình như sau ` include<bits/stdc++.h>using namespace std; const int MaxN = 1 + 1e6; int n; bool mark[MaxN]; int main(){ }
`Vậy thì độ phức tạp của thuật toán trên sẽ là bao nhiêu? Ta thấy Như vậy độ phức tạp tổng là và người ta đã chứng minh được . Do vậy, độ phức tạp của thuật toán là .. Kết luận
Tải xuốngTài liệuNhằm phục vụ mục đích học tập Offline của cộng đồng, Kteam hỗ trợ tính năng lưu trữ nội dung bài học Sàng Eratosthenes dưới dạng file PDF trong link bên dưới. Ngoài ra, bạn cũng có thể tìm thấy các tài liệu được đóng góp từ cộng đồng ở mục TÀI LIỆU trên thư viện Howkteam.com Đừng quên like và share để ủng hộ Kteam và tác giả nhé! Thảo luậnNếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng. |