# Talk:Prime numbers

### From HaskellWiki

(...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 thoseOn 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 theThrowing 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 useLOL! That is *indeed* what I meant.

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!