This isn't actually the Sieve of Eratosthenes. My undergrad advisor published a short piece about a family of functional prime generators of this form, that don't have nearly the efficiency of the true Sieve: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
The gist of the problem is this: in the true sieve, each number is touched once for each of its prime factors. In this sieve, each number is touched once by each prime smaller than it (until a factor is found.)
There are a lot more primes that aren't factors of a given number than primes that are.
I've used that paper as the impetuous for writing a few sieve algorithms (see [1] and [2]). While reasonably elegant in Haskell, my personal experience is that list-of-generator style programs cannot compare to array-based sieves for performance, due to the overhead of switching between generators all the time. Not to denigrate the main point, of course - asymptotic runtimes are far more important than implementation overheads for calculating primes.
As ahh points out in their comment, this isn't a true sieve - it's essentially trial division, although sharded between goroutines.
For comparison, I've used Go to implement a segmented version of the true Sieve of Eratosthenes. It's a standard array-based sieve, chunked up. It takes advantage of goroutines for parallelism, and implements an efficient algorithm at the same time. The code is a lot longer than this one because it tries to do a lot more (memory efficiency, large number support, etc), but it should give you an idea what a full implementation might look like. http://www.thelowlyprogrammer.com/2012/08/primes-part-2-segm...
Very cool. I ran this, adding a print statement into the Filter function so I could inspect `i` as the channels received inputs. I expected the prints to come relatively in random order but on repeated tries they didn't - and then realized I know nothing about programming with coroutines and explicit communication between threads. Thanks for the thought exercise!
// By default, Go keeps only one kernel thread (m) running user code
// at a single time; other threads may be blocked in the operating system.
// Setting the environment variable $GOMAXPROCS or calling
// runtime.GOMAXPROCS() will change the number of user threads
// allowed to execute simultaneously. $GOMAXPROCS is thus an
// approximation of the maximum number of cores to use.
Does anyone have any benchmarks on how fast this will run?
For comparison C++ based implementations range from 13.5 seconds to 0.65 seconds when iterating over 1,000,000,000 elements on an Intel Core i7 860, quad-core, hyperthreading, 2.8Ghz cpu. (http://create.stephan-brumme.com/eratosthenes/)
Does anyone know which ballpark Go is in, performance-wise? In my mind, it's a bit faster than Python, whereas I would expect it to be closer to C. However, I have no clue how I formed this opinion, so actual benchmarks would help.
"After all, facts are facts, and although we may quote one to another with a chuckle the words of the Wise Statesman, 'Lies--damned lies--and statistics,' still there are some easy figures the simplest must understand, and the astutest cannot wriggle out of." Leonard Henry Courtney, 1895
The gist of the problem is this: in the true sieve, each number is touched once for each of its prime factors. In this sieve, each number is touched once by each prime smaller than it (until a factor is found.)
There are a lot more primes that aren't factors of a given number than primes that are.