Lập trình .NET

Lập trình .NET

BT11: Tìm số nguyên tố sử dụng thuật toán Sàng Eratosthenes

1. Yêu cầu

Sàng Eratosthenes là một thuật giải toán cổ xưa để tìm các số nguyên tố nhỏ hơn 100. Thuật toán này do nhà toán học cổ Hy Lạp là Eratosthenes (Ơ-ra-tô-xten) “phát minh” ra.
Ban đầu, nhà toán học Eratosthenes sau khi tìm ra thuật toán, đã lấy lá cọ và ghi tất cả các số từ 2 cho đến 100. Ông đã chọc thủng các hợp số và giữ nguyên các số nguyên tố. Bảng số nguyên tố còn lại trông rất giống một cái sàng. Do đó, nó có tên là sàng Eratosthenes.

  • Hợp số là một số tự nhiên có thể biểu diễn thành tích của hai số tự nhiên khác nhỏ hơn nó

Giải thích:

Hình minh họa cho thấy thuật toán đơn giản để tìm số nguyên tố và các bội số. Các số tô màu giống nhau là cùng một họ, màu đậm hơn sẽ là số nguyên tố.
Để tìm các số nguyên tố nhỏ hơn hoặc bằng số tự nhiên N bằng sàng Eratosthenes, ta làm như sau:

  • Bước 1: Tạo 1 danh sách các số tự nhiên liên tiếp từ 2 đến n: (2, 3, 4,…, n).
  • Bước 2: Giả sử tất cả các số trong danh sách đều là số nguyên tố. Trong đó, p = 2 là số nguyên tố đầu tiên.
  • Bước 3: Tất cả các bội số của p: 2p, 3p, 4p,… sẽ bị đánh dấu vì không phải là số nguyên tố.
  • Bước 4: Tìm các số còn lại trong danh sách mà chưa bị đánh dấu và phải lớn hơn p. Nếu không còn số nào, dừng tìm kiếm. Ngược lại, gán cho p giá trị bằng số nguyên tố tiếp theo và quay lại bước 3.

Khi giải thuật kết thúc, tất các số chưa bị đánh dấu trong danh sách là các số nguyên tố cần tìm.


2. Thuật toán


Read một số nguyên n > 1
Khởi tạo mảng boolean  a[i] = true, i chạy từ 2 đến n,
 
for i = 2 to sqrt(n)
{
     if (a[i] is true)
     {
          for j = i*i, i*i+i, i*i+2i, i*i+3i, ..., n:
               a[j]:= false 
     } 
}
/*Nếu các phần tử a[i] vẫn = true là số nguyên tố.*/
if (a[i] == true)
    Print số nguyên tố i;

3. Video hướng dẫn

4. Code

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Share via
Copy link
Powered by Social Snap