Trang chủLập trìnhCTDL & Thuật toánTìm hiểu về thuật toán Sàng nguyên tố (sàng Eratosthenes)

Tìm hiểu về thuật toán Sàng nguyên tố (sàng Eratosthenes)

DANH SÁCH BÀI VIẾT
Cách kiểm tra Số nguyên tố trong lập trình C/C++
Đếm số lượng số nguyên tố nhỏ hơn n lập trình C/C++
Liệt kê các số nguyên tố nhỏ hơn n lập trình C/C++
Đếm số lượng số nguyên tố trong mảng lập trình C/C++
Liệt kê các số nguyên tố trong mảng lập trình C/C++
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:

  1. 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ố
  2. 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ố.
  3. 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.
  4. 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.

Minh họa thuật toán sàng nguyên tố
Minh họa thuật toán sàng nguyên tố(nguồn ảnh wikipedia)

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)
0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x