Hi Melissa, I enjoyed your article. I especially like your trick of starting with p*p. You wrote:
Which seems reasonable, until you realize that every prime p we come up with is still "considered" by k deleteOrd filters, where k is the number of primes that preceeded it.
It is true that I have never read Eritosthenes in the original, but my deleteOrd algorithm was meant to reproduce faithfully the sieve algorithm as I was taught it in grade school. We did not cross out any number more than once. But we did consider each multiple of every prime, moving on if we found it already crossed off. My algorithm does exactly the same. I do not deny that primes can be found more efficiently. But I believe that my algorithm is exactly what I was taught as the sieve. So it feels genuine to me. A few days ago, I taught the sieve to my 6 year old daughter, the same way I learned it. She loved it! She is currently working on memorizing the multiplication tables, so the sieve is intriguing to her. I'm not sure if lazy priority queues would be quite so intriguing, though. I hope I have not poisoned her mind. Regards, Yitz