>> ... he's not doing the test that something is prime, and crossing out the multiples of composites as well.
> This doesn't change the outcome, since the multiples of composites are also multiples of primes and never primes.
It doesn't change the outcome (I said that somewhere else) but it changes the algorithm. The algorithm now produces primes, yes, but it's not the Sieve of Eratosthenes.
>> ... he adds one each time to p[j], but tests to see if it's ==1, so that won't work.
> You're wrong here -- testing equality to 1 for the number of times an entry in the array was hit is exactly testing of primality post-sieve. If it was only touched once, then it has nothing that divides it (since the only cycle it was incremented on is the one starting there).
You're right, so this is definitely a different algorithm. In this algorithm what he does is:
Initialise a vector V to 0
For every number n>=2:
For every multiple m>=n of n:
Add one to V[m]
The primes are those with V[n]==1. Yes, that works, I was mistaken because I was expecting the SoE. This is not that.
>> it's certainly not the actual Sieve of Eratosthenes for any one of several reasons
> If you initialized the array entries to 1 and started indexing your inner loop at j= i \* i, it's exactly the sieve (modulo multiple strikeouts of removed numbers).
... and conditioned on striking out multiples of primes you've already identified.
There are two key components to the Sieve of Eratosthenes. One is that you walk down the vector instead of doing divisions, the other is that you identify the primes so far and only strike out those multiples.
In particular, this code must have the outer loop run all the way to n whereas the SoE only runs to sqrt(n). That's a key part of being the Sieve.
As observed by stabbles[0], the time complexity of the code presented here is worse than the time complexity of the Sieve of Eratosthenes, therefore it's a different algorithm.
> This doesn't change the outcome, since the multiples of composites are also multiples of primes and never primes.
It doesn't change the outcome (I said that somewhere else) but it changes the algorithm. The algorithm now produces primes, yes, but it's not the Sieve of Eratosthenes.
>> ... he adds one each time to p[j], but tests to see if it's ==1, so that won't work.
> You're wrong here -- testing equality to 1 for the number of times an entry in the array was hit is exactly testing of primality post-sieve. If it was only touched once, then it has nothing that divides it (since the only cycle it was incremented on is the one starting there).
You're right, so this is definitely a different algorithm. In this algorithm what he does is:
The primes are those with V[n]==1. Yes, that works, I was mistaken because I was expecting the SoE. This is not that.>> it's certainly not the actual Sieve of Eratosthenes for any one of several reasons
> If you initialized the array entries to 1 and started indexing your inner loop at j= i \* i, it's exactly the sieve (modulo multiple strikeouts of removed numbers).
... and conditioned on striking out multiples of primes you've already identified.
There are two key components to the Sieve of Eratosthenes. One is that you walk down the vector instead of doing divisions, the other is that you identify the primes so far and only strike out those multiples.
In particular, this code must have the outer loop run all the way to n whereas the SoE only runs to sqrt(n). That's a key part of being the Sieve.
As observed by stabbles[0], the time complexity of the code presented here is worse than the time complexity of the Sieve of Eratosthenes, therefore it's a different algorithm.
[0] https://news.ycombinator.com/item?id=15409394