A better concurrent prime number sieve in go

Question

After looking at the prime number sieve code, and seeing how the concurrent structure works, I found it to be extremely elegant. However, it's also extremely inefficient, and IIRC, equivalent to the O(n^2) operation of testing the divisibility of the number m by dividing it by every number less than m. I figure that I could instead modify it to use the O(n^1.5) operation of checking the divisibility of m by dividing it by every number less than or equal to the sqrt(m). However, this turned out to be a lot harder than I anticipated.

I know this is more of an algorithmics question, but it's also one extremely relevant to concurrency. How would one implement the O(n^1.5) version of the algorithm?

Answer 1

One place to look is stackoverflow, for example, the question Concurrent Prime Generator. Amongst the answers is one that uses Go and channels.

Answer 2

Elegant but inefficient prime sieve implementations are already well known to the Functional Programming community. This paper by Melissa O’Neill gives a good overview of lazy "stream" prime sieves as well as presenting efficient alternatives. (It uses Haskell, but should be a good read anyway)

Answer 3

Eratosthenes' sieve identifies prime p_i at iteration i and prunes all multiples of p_i from consideration in successive iterations. Given that, the only thing you can parallelise here is the pruning operation. This can only be sped up by a constant factor, so you won't change the big-O of the algorithm this way.