Trình trực quan hóa Sieve of Eratosthenes
Sieve of Eratosthenes hoạt hình trên lưới số — đánh dấu số nguyên tố và gạch bỏ hợp số, có điều khiển từng bước. Chạy ngay trong trình duyệt.
Mã giả
Run an operation to see its steps.
Avg · Worst
Cách dùng
- 1 Nhập giới hạn n (tối đa 150) rồi nhấn “Run sieve”.
- 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 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 Ô 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
Sieve of Eratosthenes là gì?
Đây là một thuật toán cổ để tìm tất cả số nguyên tố đến giới hạn n: liên tục lấy số chưa được đánh dấu tiếp theo (một số nguyên tố) rồi đánh dấu tất cả bội số của nó là hợp số.
Độ phức tạp thời gian của thuật toán sàng này là gì?
O(n log log n) về thời gian và O(n) về không gian bộ nhớ — nhanh hơn nhiều so với việc kiểm tra tính nguyên tố của từng số riêng lẻ.
Vì sao việc đánh dấu bắt đầu từ p² thay vì 2p?
Mọi bội số của p nhỏ hơn p² (như 2p, 3p, …) đều đã có một thừa số nguyên tố nhỏ hơn và đã được đánh dấu khi thừa số đó được xử lý trước đó, nên bắt đầu từ p² giúp tránh làm việc trùng lặp.
1 có phải là số nguyên tố không?
Không. 1 chỉ có một ước số, nên theo định nghĩa nó không phải là số nguyên tố cũng không phải hợp số — thuật toán sàng coi nó là số không nguyên tố.
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.
Trình trực quan hóa Sieve of Eratosthenes là công cụ thuật toán miễn phí của Zerethon Tools. Sieve of Eratosthenes hoạt hình trên lưới số — đánh dấu số nguyên tố và gạch bỏ hợp số, có điều khiển từng bước. Chạy ngay trong trình duyệt. Chạy hoàn toàn trong trình duyệt — không đăng ký, không tải lên.
- Danh mục
- Thuật toán
- Giá
- Miễn phí
- Quyền riêng tư
- Chạy trên trình duyệt
- Đăng ký
- Không cần
Quyền riêng tư
Dữ liệu của bạn không bao giờ rời khỏi trình duyệt trừ khi được nêu rõ. Trình trực quan hóa Sieve of Eratosthenes chạy hoàn toàn phía client — không tải lên máy chủ, không ghi log, không theo dõi dữ liệu bạn nhập.
Mới làm quen? Đọc giải thích từng bước kèm phân tích Big-O: Tìm hiểu Number Theory →
Công cụ liên quan
Trình mô phỏng Bubble Sort
Mô phỏng bubble sort có hoạt ảnh với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/hoán đổi trực tiếp và pseudocode. Chạy hoàn toàn trong trình duyệt của bạn.
Mở công cụTrình trực quan hóa Insertion Sort
Insertion Sort hoạt hình với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/ghi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt của bạn.
Mở công cụTrình trực quan hóa Selection Sort
Selection Sort hoạt hình với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/hoán đổi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt của bạn.
Mở công cụTrình trực quan hóa Merge Sort
Mô phỏng merge sort có hoạt ảnh với điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/ghi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt.
Mở công cụXây dựng, chia sẻ và phát triển trên Zerethon Social
Đăng ký miễn phí. Kiếm điểm, sưu tầm thành tựu và kết nối với nhà sáng tạo khắp thế giới.