Sieve of Eratosthenes là gì và các thuật toán thường gặp

Sieve of Eratosthenes là một kỹ thuật được xây dựng bởi một nhà toán học Hy Lạp lỗi lạc, Eratosthenes, người đã đóng góp rất nhiều vào việc xác định các số nguyên tố.

Ông đã đóng góp rất nhiều trong lĩnh vực toán học, và việc phát hiện ra sàng là điều tốt nhất mà ông đã làm trong lĩnh vực này. Nó là một mẫu hoặc thuật toán hoạt động bằng cách loại bỏ những con số không phù hợp với một kịch bản.

Sieve of Eratosthenes là gì?

Sieve of Eratosthenes là một thuật toán toán học tìm kiếm các số nguyên tố giữa hai tập hợp số.

Các mô hình sàng của Eratosthenes hoạt động bằng cách sàng lọc hoặc loại bỏ các số nhất định không đáp ứng một tiêu chí nhất định. Đối với trường hợp này, mẫu loại bỏ bội số của các số nguyên tố đã biết.

Thuật toán số nguyên tố

Số nguyên tố là số nguyên dương hoặc số nguyên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Thuật toán số nguyên tố là một chương trình được sử dụng để tìm các số nguyên tố bằng cách sàng hoặc loại bỏ các số tổng hợp. Thuật toán giúp công việc dễ dàng hơn bằng cách loại bỏ các phép chia hoặc phép nhân lặp lại phức tạp.

Sau đây là các bước dùng để tìm số nguyên tố bằng hoặc nhỏ hơn một số nguyên η cho trước.

• Liệt kê tất cả các số liên tiếp từ 2 đến η tức là (2, 3, 4, 5, ……, η).
• Gán chữ số nguyên tố đầu tiên p.
• Bắt đầu bằng p ², thực hiện phép cộng p và đánh dấu các số nguyên bằng hoặc lớn hơn p ² trong thuật toán. Các số nguyên này sẽ là p ( p + 1), p (p + 2), p ( p + 3), p ( p + 4)…
• Số không đánh dấu đầu tiên lớn hơn pđược xác định từ danh sách. Nếu số không tồn tại trong danh sách, quy trình sẽ bị tạm dừng. p tương đương với số và lặp lại bước 3.
• Sàng Eratosthenes bị dừng khi bình phương của số đang được kiểm tra vượt quá số cuối cùng trong danh sách.
• Tất cả các số trong danh sách không được đánh dấu khi thuật toán kết thúc được gọi là số nguyên tố.

ví dụ 1

Điền vào tất cả các số nguyên tố nhỏ hơn hoặc bằng 30.

Giải pháp

• Bước 1: Bước đầu tiên là liệt kê tất cả các số.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 và 30.

• Bước 2: Viết đậmtất cả các bội của 2, trừ chính 2.

2, 3, 4 , 5, 6 , 7, 8 , 9, 10 , 11, 12 , 13, 14 , 15, 16 , 17, 18 , 19, 20 , 21, 22 , 23, 24 , 25, 26 , 27, 28 , 29 và 30 .

• Bước 3: Số tiếp theo không được tô đậm là 3. Viết đậm hình vuông của nó (3 ²= 9).

2, 3, 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 , 13, 14 , 15 , 16 , 17, 18 , 19, 20 , 21 , 22 , 23, 24 , 25, 26 , 27 , 28 , 29 và 30 .

• Bước 4: Bây giờ số thứ ba không được tô màu là 5. Viết in đậm hình vuông 5 ²= 25 của nó.

2, 3, 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 , 13, 14 , 15 , 16 , 17, 18 , 19, 20 , 21 , 22 , 23, 24 , 25 , 26 , 27 , 28 , 29 và 30 .

• Bước 5: Số không bị chia thứ tư là 7 và hơn căn bậc hai là 30.
  Do đó, không có bội số nào của 7 còn lại vì chúng đã bị loại bỏ 2 và 3 lần lượt là 14, 28 và 21. Các số còn lại 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 là số nguyên tố.

Xem thêm:

Làm tròn số – Định nghĩa, Biểu đồ giá trị vị trí & Ví dụ chính xác nhất

Nhân các cấp độ nhanh chóng dễ hiểu nhất cho người mới

Ví dụ 2

Tìm các số nguyên tố từ 1 đến 100 bằng thuật toán Eratosthenes.

Giải pháp

1. Bước 1: Các số từ 1 đến 100 được liệt kê trong bảng dưới đây.

• Bước 2: Bước tiếp theo là viết đậmtất cả các bội của 2, trừ chính 2.

• Bước 3: Bây giờ tô đậmtất cả các bội số của 3, 5, 7 và chỉ để lại những số này.

• Bước 4: Vì bội số của 11, 13, 17 và 19 không có trong danh sách, nên cuối cùng 1 sẽ được tô bóng vì nó không phải là số nguyên tố.

• Bước 5: Các số không bị chia là số nguyên tố. Chúng bao gồm:

2, 3, 5,7, 11, 13,17,19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 và 97 .