Rây số nguyên tố đồng thời tốt hơn khi di chuyển

Question

Sau khi xem mã rây số nguyên tố và xem cách cấu trúc đồng thời hoạt động, tôi thấy nó cực kỳ thanh lịch. Tuy nhiên, nó cũng vô cùng không hiệu quả, và IIRC, tương đương với hoạt động O (n^2) để kiểm tra tính chia số của m bằng cách chia cho mỗi số nhỏ hơn m. Tôi thấy rằng tôi có thể thay thế sửa đổi nó để sử dụng hoạt động O (n^1.5) kiểm tra tính chia rẽ của m bằng cách chia cho mỗi số nhỏ hơn hoặc bằng sqrt (m). Tuy nhiên, điều này hóa ra lại khó hơn rất nhiều so với dự đoán của tôi.

Tôi biết đây là câu hỏi về thuật toán nhiều hơn, nhưng cũng là một câu hỏi cực kỳ có liên quan đến đồng thời. Làm cách nào để triển khai phiên bản O (n^1.5) của thuật toán?

Answer 1

Một nơi để xem là stackoverflow, ví dụ: câu hỏi Concurrent Prime Generator. Trong số các câu trả lời là câu trả lời sử dụng Go and channels.

Answer 2

Việc triển khai rây thanh lịch nhưng không hiệu quả đã được cộng đồng lập trình chức năng biết rõ. Điều này paper bởi Melissa O’Neill cho một cái nhìn tổng quan tốt về lười biếng "dòng" nguyên tố sàng cũng như trình bày lựa chọn thay thế hiệu quả. (Nó sử dụng Haskell, nhưng phải là một đọc tốt anyway)

Answer 3

Rây Eratosthenes xác định p_i nguyên tố khi lặp lại i và làm cho tất cả các bội số của p_i được xem xét trong các lần lặp liên tiếp. Cho rằng, điều duy nhất bạn có thể song song ở đây là hoạt động cắt tỉa. Điều này chỉ có thể được tăng tốc bởi một yếu tố không đổi, vì vậy bạn sẽ không thay đổi big-O của thuật toán theo cách này.