[Haskell-cafe] Re: Genuine Eratosthenes sieve [Was: Optimization fun]

[Yitzchak Gale]

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