Tại http://cr.yp.to/primegen.html bạn có thể tìm thấy nguồn chương trình sử dụng sàng của Atkin để tạo số nguyên tố. Như tác giả nói rằng có thể mất vài tháng để trả lời một e-mail gửi cho anh ta (tôi hiểu rằng, anh ấy chắc chắn là một người đàn ông bị chiếm đóng!) Tôi đang đăng câu hỏi này.Giới hạn của 10^15 trong D.J. Chương trình 'thủ tướng' của Bernstein đến từ đâu?
Trang tuyên bố rằng 'nguyên tố có thể tạo số nguyên tố lên đến 1000000000000000'. Tôi đang cố gắng hiểu tại sao nó lại như vậy. Tất nhiên có một giới hạn lên đến 2^64 ~ 2 * 10^19 (kích thước của int không dấu dài) vì đây là cách các số được biểu diễn. Tôi biết chắc chắn rằng nếu có một khoảng trống lớn (> 2^31) thì việc in các số sẽ thất bại. Tuy nhiên trong phạm vi này tôi nghĩ rằng không có khoảng cách chính như vậy.
Hoặc tác giả đã đánh giá quá cao giới hạn (và thực sự là khoảng 10^19) hoặc có một vị trí trong mã nguồn nơi hoạt động số học có thể tràn hoặc tương tự như vậy.
Điều buồn cười là bạn thực sự có thể chạy nó cho số> 10^15:
./primes 10000000000000000 10000000000000100
10000000000000061
10000000000000069
10000000000000079
10000000000000099
và nếu bạn tin rằng Wolfram Alpha, nó là đúng.
Một số thông tin tôi đã "đảo ngược chế":
- số được rây theo lô của 1.920 * PRIMEGEN_WORDS = 3.932.160 số (xem chức năng primegen_fill trong primegen_next.c)
- PRIMEGEN_WORDS điều khiển lớn như thế nào một đơn sifting là - bạn có thể điều chỉnh nó trong primegen_impl.h để phù hợp với bộ nhớ cache CPU của bạn,
- việc thực hiện rây chính nó là trong tập tin primegen.c - Tôi giả sử nó là chính xác; những gì bạn nhận được là một bitmask của số nguyên tố trong pg-> buf (xem hàm primegen_fill)
- Bitmask được phân tích và số nguyên tố được lưu trữ trong mảng pg-> p.
Tôi không thấy điểm nào xảy ra tràn.
Tôi không nhớ, nhưng giả sử DJB sử dụng số nguyên không dấu cho số nguyên tố sàng (số 32 bit) và giả định số nguyên không dấu cho số nguyên tố được tạo bởi rây (do đó số 64 bit) giới hạn trên thuật toán thực sự là 2^64. Nhận xét của DJB có thể là giới hạn _practical_, vì việc sàng lọc ở phạm vi đó mất rất nhiều thời gian. – user448810