DANH SÁCH BÀI VIẾT Tìm hiểu thuật toán Quy hoạch động Tìm hiểu về Hàm đệ quy Thuật toán tìm kiếm nhị Tìm hiểu về Thuật toán quay lui (Backtracking) Tìm hiểu thuật toán Loang Tìm hiểu thuật toán chia để trị Tìm hiểu thuật toán tham lam trong lập trình Giải thuật tìm kiếm theo chiều sâu DFS (Depth First Search) Giải thuật tìm kiếm theo chiều rộng BFS (Breadth-first search) Tìm hiểu về thuật toán Sàng nguyên tố (sàng Eratosthenes)
Sàng nguyên tố là một thuật toán giúp nhanh chóng liệt kê các số nguyên tố. Đây là một thuật toán tìm số nguyên tố tối ưu khi muốn tìm tất cả các số nguyên tố nhỏ hơn một số N cho trước.
Thuật toán này được nhà toán học Eratosthenes phát hiện, nên chúng ta thường hay gọi thuật toán này gắn với tên của ông là Sàng Eratosthenes.
vậy trong bài viết hôm nay chúng ta cùng đi tìm hiểu thuật toán này nhé.
Thuật toán Sàng nguyên tố
Một số nguyên tố là số chỉ có 2 ước là 1 và chính nó. Do vậy, nếu ta xác định được số x là số nguyên tố, ta có thể kết luận mọi số là bội của số x thì số đó không phải là số nguyên tố, từ đây ta có thể bỏ bất rất nhiều số không cần kiểm tra và tiết kiệm được thời gian xử lý thuật toán.
Ta lấy ví dụ như sau
Số 2 là số nguyên tố => các số 4, 6, 8, 10, ... không phải số nguyên tố.
Số 3 là số nguyên tố => các số 9, 15, 21, ... không phải số nguyên tố.
Vậy có thể rút ra ý tưởng của thuật toán như sau:
- Tạo mảng đánh dấu cho tất cả các phần tử từ 2 đến N và mặc định tất cả đều là số nguyên tố
- Xét số đầu tiên tìm được là số nguyên tố – giả sử x, đánh dấu tất cả các ước của x: 2x, 3x, 4x,… trong đoạn [x, N] không phải số nguyên tố.
- Tìm số tiếp theo được đánh dấu là số nguyên tố trong [x, N]. Nếu không còn số nào, thoát chương trình. Nếu còn, gán nó bằng x và lặp lại bước 2.
- Khi kết thúc giải thuật, các số không bị đánh dấu là các số nguyên tố
Xem hình minh họa dưới đây để hiểu rõ hơn.
Cài đặt thuật toán trên C/C++
#include <stdio.h>
//Hàm dàng nguyên tố
void sangEratosthenes(int n, bool check[]){
for (int i = 2; i <= n; i++) {
// Nếu một số là số nguyên tố, thì tất cả các bội của nó không phải số nguyên tố
if (check[i] == true) {
for (int j = 2 * i; j <= n; j += i) {
check[j] = false;
}
}
}
}
int main() {
int n = 5000;
bool check[n + 1];
// Khởi tạo tất cả các số [2...N] đều là số nguyên tố
for (int i = 2; i <= n; i++) {
check[i] = true;
}
//Gọi hàm sàng nguyên tố
sangEratosthenes(n, check);
//Hiển thị các số nguyên tố nhỏ hơn n ra màn hình
for (int i = 2; i <= n; i++) {
if (check[i] == true) {
printf("%d ", i);
}
}
}
[Xem tất cả bài viết chủ đề C/C++ tại đây]
XEM THÊM Thuật toán tìm kiếm nhị phân trong C/C++ Thuật toán tính dãy số Fibonacci bằng 3 cách trong C/C++ Thuật toán đếm số lượng chữ số của số nguyên dương n bằng C / C++ Thuật toán sắp xếp nhanh (Quick Sort)
