Personal tools

Talk:Prime numbers

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
('re right, you know...)
(comment on difference between prime filtering and sieve-ing)

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
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
filtering in
is in fact unecessary. The function works just fine without it. (Notice I have made some edits to correct the multiple bugs in the
function. Oops!) Now the only use of
is in the
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!