Personal tools

Talk:Prime numbers

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(...you're right, you know...)
(comment on difference between prime filtering and sieve-ing)
Line 20: Line 20:
[[User:MathematicalOrchid|MathematicalOrchid]] 10:17, 6 February 2007 (UTC)
[[User:MathematicalOrchid|MathematicalOrchid]] 10:17, 6 February 2007 (UTC)
 +
 +
The section [[Prime_numbers#Simple_Prime_Sieve_II|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
 +
 +
<hask>
 +
primes :: [Integer]
 +
primes = sieve [2..]
 +
where sieve (p:xs) = p : sieve [x | x<-xs, (x< p*p) || (x `mod` p /= 0)]
 +
</hask>
 +
 +
However, this runs even slower than the original!

Revision as of 06:39, 4 February 2009

Here's an interesting question: will the program go faster if we replace all those
(n >)
expressions with
(\x -> floor (sqrt n) > x)
?

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
takeWhile
at all?

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
(\x -> n > x*x)
--Johannes Ahlmann 21:18, 5 February 2007 (UTC)

LOL! That is indeed what I meant.

It turns out my comment above is correct - the
takeWhile
filtering in
factors
is in fact unecessary. The function works just fine without it. (Notice I have made some edits to correct the multiple bugs in the
primes
function. Oops!) Now the only use of
takeWhile
is in the
is_prime
function, which could be changed to 'give up' the search a lot faster and hence confirm large primes with much less CPU time and RAM usage. Maybe I'll wrap my brain around that later.

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 :: [Integer]
  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!

Retrieved from "http://www.haskell.org/haskellwiki/Talk:Prime_numbers"