I would be interested in seeing a multithreaded solution, with each
child thread crossing off the multiples of its own prime. The parent
thread would be blocked from spawning a new thread for multiples of the
next prime p until all existing child threads are past p.
It is not clear to me what
Yitzchak Gale wrote:
Melissa O'Neill wrote:
- Eratosthenes's sieve never says the equivalent of, Hmm, I
wonder if 19 is a multiple of 17 -- but both the basic sieve we
began with and the deleteOrd version do
So then maybe I taught my daughter the wrong thing.
When she does 17, she
The point about Eratosthenes's sieve is that it does not specify
algorithmically how to find the next number to be crossed. It does not
even define how to store (crossed) numbers, it stores them on paper.
But , I believe that Eratosthenes's sieve does specify how to store numbers
and how to
Jens Blanck wrote:
The point about Eratosthenes's sieve is that it does not specify
algorithmically how to find the next number to be crossed. It does not
even define how to store (crossed) numbers, it stores them on paper.
But , I believe that Eratosthenes's sieve does specify how to store
Sorry, I'm a little late to this thread, but the topic of
sieve [] = []
sieve (x:xs) = x : sieve [y | y - xs, y `mod` x /= 0]
(as posted by Rafael Almeida) is somewhat dear to my heart, as I
wrote a paper about it last summer and sent it in to JFP. Still
waiting for a reply though.
Let's
You took my quote entirely out of context. In particular, you omitted
the rest of the sentence but I'm sure that day will come. My
statement was no excuse by any stretch of the imagination--I was
initially confused when I saw it in your post and then a bit offended.
The original intent of my
Melissa O'Neill wrote:
FWIW, another way to write this code (without needing to think about how
fold bails early) is
primes = 2: [x | x −[3,5..], all (\p − x `mod` p 0) (factorsToTry x)]
where
factorsToTry x = takeWhile (\p − p*p = x) primes
Well, you certainly thought of the fact
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
apfelmus wrote:
I think that the `mod`-algorithm counts as sieve, it just does a
bad job at organizing the crossing off.
I'd say that it might count as a sieve, but *algorithmically* it is
not The Sieve of Eratosthenes. If you abstract away the
algorithmic details to a mathematical
