Trình trực quan hóa Sieve of Eratosthenes

Cách dùng

1. 1 Nhập giới hạn n (tối đa 150) rồi nhấn “Run sieve”.
2. 2 Xem từng số nguyên tố được đánh dấu, sau đó tất cả bội số của nó bị gạch bỏ vì là hợp số.
3. 3 Lùi lại và tiến tới từng bước, hoặc dùng “Random” để chọn giới hạn khác.
4. 4 Ô màu xanh lá là số nguyên tố, ô màu xám là hợp số.

Vì sao dùng công cụ này

• Hiểu vì sao thuật toán sàng chỉ cần bắt đầu đánh dấu từ p² với mỗi số nguyên tố p.
• Xem các hợp số dần biến mất, chỉ còn lại các số nguyên tố được làm nổi bật.
• Hiểu độ phức tạp thời gian gần tuyến tính O(n log log n).
• Chạy hoàn toàn trong trình duyệt của bạn. Không cần đăng ký, không cần tải lên.

Câu hỏi thường gặp

Trình trực quan hóa Sieve of Eratosthenes là gì?

Trình trực quan hóa Sieve of Eratosthenes minh họa động thuật toán tìm số nguyên tố kinh điển này: bắt đầu từ 2, nó đánh dấu mỗi số chưa được đánh dấu là số nguyên tố rồi gạch bỏ tất cả bội số của số đó là hợp số, cuối cùng chỉ còn lại các số nguyên tố đến n.

Tính năng

Ví dụ

primes up to 30

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Trường hợp sử dụng

1. 1

   Liệt kê số nguyên tố nhanh chóng

   Tạo danh sách tất cả số nguyên tố nhỏ hơn một giới hạn cho trước một cách hiệu quả.

2. 2

   Tính toán trước cho các bài toán

   Xây dựng bảng số nguyên tố phục vụ các bài toán lý thuyết số hoặc lập trình thi đấu.

3. 3

   Hiểu ý tưởng của thuật toán sàng

   Thấy rõ vì sao việc đánh dấu bội số hiệu quả hơn kiểm tra nguyên tố từng số một.

Tài liệu tham khảo

• Sieve of Eratosthenes — Wolfram MathWorld — Wolfram MathWorld
• Sieve of Eratosthenes — Wikipedia