WillNess/gist:5690320

## gistfile1.txt
Hmm, very interesting. Your code is actual honest to goodness ***genuine sieve of Eratosthenes*** IMHO, counting its way along the ascending natural numbers by decrementing each counter that it sets up for each prime encountered, by 1 on each step.

And it is very inefficient. [Tested on Ideone](http://ideone.com/EC3t4g) it runs at the same empirical order of growth `~ n^2.2` (at the tested range of few thousand primes produced) as the famously inefficient [Turner's trial division sieve](http://ideone.com/cWYH4g) (in Haskell).

Why? Several reasons. ***First***, no early bailout in your test: when you detect it's a composite, you continue processing the array of counters, `sieve`. You have to, because of the ***second reason***: you count the difference by decrementing each counter by 1 on each step, with 0 representing your current position. This is the most faithful expression of the original sieve IMHO, and it is very inefficient: today our CPUs know how to add numbers in O(1) time (if those numbers belong to a certain range, 0 .. 2^32, or 0 .. 2^64, of course).

Moreover, our computers also have random access memory now, and having calculated the far-off number we can mark it in a random access array. Which is the foundation of the efficiency of the sieve of Eratosthenes on modern computers - both the direct calculation, and the direct marking.

The ***third***, not less important reason for inefficiency, is the premature handling of the multiples: when you encounter 5 as a prime, you add its first multiple (not yet encountered) i.e. 25, *right away* into the array of counters, `sieve` (i.e. the distance between current point and the value `i*i-i`). That is much too soon. The addition of 25 must be ***postponed*** until ... well, until we encounter it among the ascending natural numbers. Starting to handle the multiples of each prime too early (at `p` instead of `p*p`) leads to having way too many counters to maintain - `O(n)` of them (where `n` is the number of primes produced), instead of just `O(sqrt(n))`.
	Hmm, very interesting. Your code is actual honest to goodness *genuine sieve of Eratosthenes* IMHO, counting its way along the ascending natural numbers by decrementing each counter that it sets up for each prime encountered, by 1 on each step.

	And it is very inefficient. [Tested on Ideone](http://ideone.com/EC3t4g) it runs at the same empirical order of growth `~ n^2.2` (at the tested range of few thousand primes produced) as the famously inefficient [Turner's trial division sieve](http://ideone.com/cWYH4g) (in Haskell).

	Why? Several reasons. *First, no early bailout in your test: when you detect it's a composite, you continue processing the array of counters, `sieve`. You have to, because of the second reason*: you count the difference by decrementing each counter by 1 on each step, with 0 representing your current position. This is the most faithful expression of the original sieve IMHO, and it is very inefficient: today our CPUs know how to add numbers in O(1) time (if those numbers belong to a certain range, 0 .. 2^32, or 0 .. 2^64, of course).

	Moreover, our computers also have random access memory now, and having calculated the far-off number we can mark it in a random access array. Which is the foundation of the efficiency of the sieve of Eratosthenes on modern computers - both the direct calculation, and the direct marking.

	The *third, not less important reason for inefficiency, is the premature handling of the multiples: when you encounter 5 as a prime, you add its first multiple (not yet encountered) i.e. 25, right away* into the array of counters, `sieve` (i.e. the distance between current point and the value `ii-i`). That is much too soon. The addition of 25 must be postponed* until ... well, until we encounter it among the ascending natural numbers. Starting to handle the multiples of each prime too early (at `p` instead of `p*p`) leads to having way too many counters to maintain - `O(n)` of them (where `n` is the number of primes produced), instead of just `O(sqrt(n))`.