Cổng Thông Tin Đại Học, Cao Đẳng Lớn Nhất Việt Nam

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.

Sieve of Eratosthenes là gì?
Sieve of Eratosthenes là gì?

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 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 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ố.
Thuật toán số nguyên tố
Thuật toán 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 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.
1234567số 8910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100
  • 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.
1234567số 8910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100
  • 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.
1234567số 8910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100
  • 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ố.
1234567số 8910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100
  • 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 .

0 0 votes
Article Rating
Theo dõi
Thông báo của
guest
0 Comments
Inline Feedbacks
View all comments

Khoa Y Dược Hà Nội tuyển sinh chính quy & liên thông vb2 các ngành Y Dược

Du học & XKLD Hướng tới 1 tương lai phát triển hơn

ĐỌC TRUYỆN HAY NHẤT

Bài viết mới nhất

https://tintuctuyensinh.vn/wp-content/uploads/2021/04/2.jpg
0
Would love your thoughts, please comment.x
()
x