Thuật toán Eratosthenes – Tối ưu thuật toán sàng số nguyên tố

1. Giới thiệu:

– Thuật toán Eratosthenes là thuật toán cổ xưa của người Hy Lạp để tìm một lượng số nguyên tố trong một phạm vi nhất định.

– Trong trường hợp muốn tìm tất cả các số nguyên tố trong một phạm vi lớn, việc sử dụng thuật toán sàng Eratosthenes sẽ mang lại hiệu quả cao về tốc độ thực hiện.

– Các bước của thuật toán sàng Eratosthenes:

+ Bước 1: Khởi tạo một tập hợp các số từ 2 đến N, trong đó N là phạm vi cần tìm

+ Bước 2: Từ 2, ta sẽ đánh dấu tất cả các bội của 2 và các bội này phải < N, những số được đánh dấu không phải là số nguyên tố. Sau khi đánh dấu hết tất cả các bội của 2, ta tiến hành đánh dấu bội của 3, 5 …. ta bỏ qua số 4 vì nó là bội của 2 và đã được đánh dấu.

+ Bước 3: Những số còn lại không được đánh dấu là số nguyên tố.

2. Cài đặt:

Sau đây, tôi sẽ trình bày phần hiện thực thuật toán.
Thông thường, chúng ta sẽ duyệt lại tập hợp sau khi đã sàng lọc.
Trong phần này, tôi sẽ tối ưu thuật toán bằng cách vừa sàng vừa hiển thị kết quả để tăng tốc độ thuật toán.

 Hình 1 – Khởi tạo và gọi hàm:

1

Hình 1

Hình 2 – Cài đặt thuật toán Eratosthenes:

1

Hình 2

Hình 3 – Đánh dấu các bội của một số nguyên tố:

1

Hình 3

Như vậy là tôi vừa hướng dẫn các bạn cài đặt và tối ưu thuật toán Eratosthenes.

Chúc các bạn thành công!

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s