# Difference between revisions of "Talk:Prime numbers"

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)