Bỏ qua nội dung

Sieve of Eratosthenes

Lưới Eratosthenes

Nhà toán học Hy Lạp Eratosthenes đã tìm ra các số nguyên tố mà không chia bất cứ số nào: viết ra các số, sau đó gạch bỏ các bội số của mỗi số nguyên tố.

Hàm [True] * (n + 1) tạo ra một danh sách chứa n + 1 giá trị True, một giá trị cho mỗi số từ 0 đến n. Đánh dấu 0 và 1 là không phải số nguyên tố. Sau đó, với mỗi p vẫn còn được đánh dấu là True, đặt mọi bội số của p từ p * p trở lên thành False. Những số vẫn còn được đánh dấu là True ở cuối cùng chính là các số nguyên tố.

Đăng nhập hoặc tạo tài khoản

IGCSE, A-Level & AP