Về sàng Eratosthenes - cách sàng số nguyên tố hoạt động

Eratosthenes xứ Cyrene

Eratosthenes sống vào khoảng năm 276 đến 194 trước Công nguyên và đứng đầu Thư viện lớn Alexandria. Ông nổi tiếng nhất vì đã đo kích thước Trái Đất từ độ dài bóng nắng ở hai thành phố. Sàng mang tên ông vì Nicomachus xứ Gerasa đã mô tả nó là phương pháp của ông trong cuốn Nhập môn số học, viết vào khoảng năm 100 sau Công nguyên.

Cách sàng hoạt động

Viết các số từ 2 đến N. Số đầu tiên, 2, là số nguyên tố: gạch 4, 6, 8 và mọi bội khác của 2. Số tiếp theo còn lại, 3, là số nguyên tố: gạch 9, 12, 15 và cứ thế. Tiếp tục với 5, 7 và các số tiếp theo còn lại. Một số không bao giờ bị gạch thì không có ước nhỏ hơn, nên nó là số nguyên tố.

Dừng ở căn bậc hai

Mọi hợp số đến N đều có một ước nguyên tố không lớn hơn căn bậc hai của N. Vì vậy ngay khi p² lớn hơn N, không còn gì để gạch nữa. Để tìm các số nguyên tố đến 100 bạn chỉ cần 2, 3, 5 và 7, còn đến 1000 thì cần các số nguyên tố đến 31.

Sàng nhanh đến mức nào?

Sàng cần khoảng N log log N bước, chỉ tăng nhanh hơn N một chút. Máy tính vẫn dùng nó, thường theo từng đoạn dưới dạng sàng phân đoạn, để liệt kê số nguyên tố đến hàng tỷ. Để kiểm tra một số lớn có phải số nguyên tố hay không, các phương pháp khác nhanh hơn.

Hỏi thường xuyên

Ai phát minh ra sàng Eratosthenes?

Sàng được đặt theo tên Eratosthenes xứ Cyrene, một học giả Hy Lạp thế kỷ thứ ba trước Công nguyên. Mô tả bằng văn bản cổ nhất còn lại là của Nicomachus xứ Gerasa, khoảng năm 100 sau Công nguyên.

Tại sao sàng bắt đầu gạch từ p²?

Mọi bội nhỏ hơn của p đều có một ước nguyên tố nhỏ hơn, nên một số nguyên tố nhỏ hơn đã gạch nó rồi.

Có bao nhiêu số nguyên tố dưới 1000?

Có 168 số nguyên tố dưới 1000. Số lớn nhất là 997.