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

Thẳng tiến vào ĐH chỉ với : Điểm lớp 12 Từ 6,5 – Điểm thi từ 18 năm 2021Sieve of Eratosthenes là một kỹ thuật được thiết kế xây dựng bởi một nhà toán học Hy Lạp lỗi lạc, Eratosthenes, người đã góp phần rất nhiều vào việc xác lập những số nguyên tố .

Ông đã góp phần rất nhiều trong nghành 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 nghành này. Nó là một mẫu hoặc thuật toán hoạt động giải trí bằng cách vô hiệu những số lượng không tương thích với một ngữ cảnh .

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 quy mô sàng của Eratosthenes hoạt động giải trí bằng cách sàng lọc hoặc vô hiệu những số nhất định không cung ứng một tiêu chuẩn nhất định. Đối với trường hợp này, mẫu vô hiệu bội số của những 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 những số nguyên tố bằng cách sàng hoặc vô hiệu những số tổng hợp. Thuật toán giúp việc làm thuận tiện hơn bằng cách vô hiệu những phép chia hoặc phép nhân lặp lại phức tạp .

Sau đây là những bước dùng để tìm số nguyên tố bằng hoặc nhỏ hơn 1 số ít 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 2, 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 2 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 toàn bộ những 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 2= 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 2= 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 .