Personal tools

Talk:Prime numbers

From HaskellWiki

Revision as of 21:18, 5 February 2007 by JohannesAhlmann (Talk | contribs)

Jump to: navigation, search
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)