5 ms·

He's adding i, not 1, to j on every inner loop. Basically he's incrementing any array element that is a multiple of 2, then of 3, etc.

ColinWright 9y ago
Then 4, then 5, then 6 ... in other words he's not doing the test that something is prime, and crossing out the multiples of composites as well. There are other problems as well, he adds one each time to p[j], but tests to see if it's ==1, so that won't work. So while the output might be right (but it isn't), it's certainly not the actual Sieve of Eratosthenes for any one of several reasons.
- SomeStupidPoint 9y ago
  > in other words 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. > There are other problems as well, 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). > 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).
  - ColinWright 9y ago
    >> ... 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. [0] https://news.ycombinator.com/item?id=15409394 https://news.ycombinator.com/item?id=15409394
- IncRnd 9y ago
  Your review of the code was incorrect. The code tests primality with the ==1 check that you say is wrong. Why do you say that the output is wrong?
  - ColinWright 9y ago
    I was wrong when I claimed the output would be wrong - see my comments here[0]. The output is correct, but the code is not the Sieve of Eratosthenes. I was misled by the expectation that it would be. [0] https://news.ycombinator.com/item?id=15410300 https://news.ycombinator.com/item?id=15410300
    - IncRnd 9y ago
      Good point. The loop's upper-bound check differs. Thanks!

ColinWright 9y ago

Then 4, then 5, then 6 ... in other words he's not doing the test that something is prime, and crossing out the multiples of composites as well. There are other problems as well, he adds one each time to p[j], but tests to see if it's ==1, so that won't work. So while the output might be right (but it isn't), it's certainly not the actual Sieve of Eratosthenes for any one of several reasons.

SomeStupidPoint 9y ago
> in other words 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. > There are other problems as well, 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). > 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).
- ColinWright 9y ago
  >> ... 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. [0] https://news.ycombinator.com/item?id=15409394 https://news.ycombinator.com/item?id=15409394
IncRnd 9y ago
Your review of the code was incorrect. The code tests primality with the ==1 check that you say is wrong. Why do you say that the output is wrong?
- ColinWright 9y ago
  I was wrong when I claimed the output would be wrong - see my comments here[0]. The output is correct, but the code is not the Sieve of Eratosthenes. I was misled by the expectation that it would be. [0] https://news.ycombinator.com/item?id=15410300 https://news.ycombinator.com/item?id=15410300
  - IncRnd 9y ago
    Good point. The loop's upper-bound check differs. Thanks!