Trong thực tế, người ta có thể thực hiện một Sieve of Atkin không bị chặn (SoA) không sử dụng phân đoạn ở tất cả như tôi đã làm here in F#. Lưu ý rằng đây là một phiên bản chức năng thuần túy mà thậm chí không sử dụng các mảng để kết hợp các giải pháp của phương trình bậc hai và bộ lọc hình vuông và do đó chậm hơn đáng kể so với cách tiếp cận cấp bách hơn.
Tối ưu hóa của Berstein khi sử dụng bảng tra cứu cho phạm vi 32 bit tối ưu sẽ khiến mã cực kỳ phức tạp và không phù hợp để trình bày ở đây, nhưng sẽ khá dễ dàng để điều chỉnh mã F # của tôi sao cho chuỗi bắt đầu và chỉ được sử dụng trên một phạm vi để triển khai phiên bản được phân đoạn và/hoặc áp dụng các kỹ thuật tương tự cho phương pháp tiếp cận cấp bách hơn bằng cách sử dụng mảng. Lưu ý rằng ngay cả việc thực hiện SoA của Berstein không thực sự nhanh hơn Sàng Eratosthenes với tất cả các tối ưu hóa có thể theo Kim Walisch's primesieve nhưng chỉ nhanh hơn phiên bản tối ưu tương đương của Sàng Eratosthenes cho phạm vi số được chọn theo yêu cầu của anh ta.
EDIT_ADD: Đối với những người không muốn lội qua mã giả và mã C của Berstein, tôi thêm vào câu trả lời này để thêm phương pháp mã giả để sử dụng SoA trong phạm vi từ LOW đến HIGH vùng đồng bằng từ LOW đến HIGH + 1 có thể bị hạn chế với một modulo 60 thậm chí để sử dụng các tối ưu hóa modulo (và bit tiềm năng để chỉ các mục trên ổ đĩa 2,3,5) tối ưu hóa.
Điều này được dựa trên việc triển khai có thể bằng cách sử dụng tứ giác SoA của (4 * x^2 + y ^), (3 * x^2 + y^2) và (3 * x^2 -y^2) được biểu diễn bằng các chuỗi số có giá trị x cho mỗi chuỗi được cố định với các giá trị giữa một và SQRT ((HIGH - 1)/4), SQRT ((HIGH - 1)/3) và giải phương trình bậc hai cho 2 * x^2 + 2 * x - CAO - 1 = 0 cho x = (SQRT (1 + 2 * (HIGH + 1)) - 1)/2, tương ứng, với các chuỗi được biểu diễn trong mã F # của tôi theo liên kết trên cùng . Tối ưu hóa các chuỗi có sử dụng khi rây các vật liệu tổng hợp lẻ, đối với chuỗi "4x", giá trị y chỉ cần lẻ và chuỗi "3x" chỉ cần sử dụng giá trị lẻ của y khi x là đồng đều và ngược lại. Tối ưu hóa hơn nữa giảm số lượng các giải pháp cho phương trình bậc hai (= các phần tử trong dãy) bằng cách quan sát rằng các mẫu modulo trên các dãy trên lặp lại trên các phạm vi rất nhỏ của x và cũng lặp lại trong phạm vi y chỉ 30, được sử dụng trong mã Berstein nhưng chưa được thực hiện trong mã F # của tôi.
Tôi cũng không bao gồm các tối ưu hóa nổi tiếng có thể được áp dụng cho việc tách "ô vuông" chính để sử dụng hệ số bánh xe và các tính toán cho địa chỉ phân đoạn bắt đầu như tôi sử dụng trong my implementations of a segmented SoE.
Vì vậy, với mục đích tính toán địa chỉ đoạn bắt đầu chuỗi cho "4x", "3x +" và "3x-" (hoặc với "3x +" và "3x-" được kết hợp như tôi thực hiện trong mã F #), và khi tính toán phạm vi của x cho mỗi theo trên, pseudo-code như sau:
tính loạt LOW - FIRST_ELEMENT, nơi FIRST_ELEMENT là có giá trị áp dụng thấp nhất của y đối với từng giá trị nhất định của x hoặc y = x - 1 cho trường hợp của chuỗi "3x".
Để tính toán có bao nhiêu phần tử trong phạm vi này, điều này sẽ giải thích câu hỏi có bao nhiêu (y1)^2 + (y2)^2 + (y3)^2 ... có trong đó mỗi số y được phân cách bằng hai số, để tạo ra số chẵn hoặc lẻ theo yêu cầu. Như thường lệ trong phân tích trình tự vuông, chúng ta quan sát thấy sự khác biệt giữa các ô có tăng gia tăng như trong delta (9 - 1) là 8, delta (25 - 9) là 16 cho tăng 8, delta (49 - 25) là 24 để tăng thêm 8, v.v. để cho các phần tử n, gia số cuối cùng là 8 * n cho ví dụ này. Thể hiện trình tự của các phần tử bằng cách sử dụng này, chúng tôi nhận được nó là một (hoặc bất kỳ cái nào được chọn làm phần tử đầu tiên) cộng với tám lần trình tự của một cái gì đó như (1 + 2 + 3 + ... + n). Bây giờ giảm tiêu chuẩn các chuỗi tuyến tính áp dụng khi tổng này là (n + 1) * n/2 hoặc n^2/2 + n/2. Điều này chúng ta có thể giải quyết cho bao nhiêu phần tử n có trong phạm vi bằng cách giải phương trình bậc hai n^2/2 + n/2 - phạm vi = 0 hoặc n = (SQRT (8 * phạm vi + 1) - 1)/2.
Bây giờ, nếu FIRST_ELEMENT + 4 * (n + 1) * n không bằng LOW làm địa chỉ xuất phát, hãy thêm một vào n và sử dụng FIRST_ELEMENT + 4 * (n + 2) * (n + 1) làm địa chỉ bắt đầu. Nếu người ta sử dụng tối ưu hóa thêm để áp dụng hệ số bánh xe culling vào mẫu trình tự, tìm kiếm mảng bảng có thể được sử dụng để tìm kiếm giá trị gần nhất của n được sử dụng đáp ứng các điều kiện.
Mô đun 12 hoặc 60 của phần tử bắt đầu có thể được tính toán trực tiếp hoặc có thể được tạo ra bằng cách sử dụng tra cứu bảng dựa trên bản chất lặp lại của chuỗi modulo.
Mỗi trình tự sau đó được sử dụng để chuyển trạng thái hỗn hợp lên đến giới hạn HIGH. Nếu logic bổ sung được thêm vào các chuỗi để nhảy các giá trị giữa chỉ các phần tử áp dụng cho mỗi chuỗi, thì không cần sử dụng thêm các điều kiện modulo nữa.
Ở trên được thực hiện cho mọi chuỗi "4x", sau đó là chuỗi "3x +" và "3x" (hoặc kết hợp "3x +" và "3x-" vào chỉ một bộ chuỗi "3x") x giới hạn như được tính toán trước đó hoặc được thử nghiệm trên mỗi vòng lặp.
Và ở đó bạn có nó: đưa ra phương pháp phân chia dải sàng thành các phân đoạn phù hợp nhất. SoA giống như được sử dụng bởi Bernstein nhưng hơi đơn giản trong biểu thức như nó đề cập nhưng không kết hợp các hoạt động modulo và đóng gói bit.
Tôi đã nghiên cứu sàng Atkin/Bernstein trong nhiều năm và không bao giờ tìm ra cách để phân đoạn - theo ý tôi, để bắt đầu với số lượng lớn tùy ý, có thể có một chút tiền xử lý. Tôi muốn được quan tâm để xem nếu có ai. – librik