(comment on difference between prime filtering and sieve-ing)
m (added signature)
Revision as of 06:45, 4 February 2009Here's an interesting question: will the program go faster if we replace all those
On one hand, a composite integer cannot possess a factor greater than its square root.On the other hand, since the list we're looking through contains all possible prime numbers, we are guaranteed to find a factor or an exact match eventually, so do we need the
Throwing this over to somebody with a bigger brain than me...
MathematicalOrchid 16:41, 5 February 2007 (UTC)
a composite can indeed have factors greater than its square root, and indeed most do. what you mean is that a composite will definitely have at least one factor smaller-equal than its square root.why not use
LOL! That is indeed what I meant.It turns out my comment above is correct - the
MathematicalOrchid 10:17, 6 February 2007 (UTC)
The section Simple Prime Sieve II is not a sieve in the same sense that the first one is. It really implements a primality test as a filter.
A more "sieve-like" version of the simple sieve which exploits the fact that we need not check for primes larger than the square root would be
primes = sieve [2..]
where sieve (p:xs) = p : sieve [x | x<-xs, (x< p*p) || (x `mod` p /= 0)]
However, this runs even slower than the original!
Kapil Hari Paranjape 06:51, 4 February 2009 (UTC)