# 99 questions/Solutions/31

### From HaskellWiki

< 99 questions | Solutions(Difference between revisions)

(change the 2nd version code) |
(leaving just one solution in.) |
||

Line 1: | Line 1: | ||

(**) Determine whether a given integer number is prime. | (**) Determine whether a given integer number is prime. | ||

− | ''' | + | Well, a natural number ''k'' is a prime number if it is larger than '''1''' and no natural number ''n >= 2'' with ''n^2 <= k'' is a divisor of ''k''. However, we don't actually need to check all natural numbers ''n <= sqrt k''. We need only check the '''''primes''' p <= sqrt k'': |

<haskell> | <haskell> | ||

isPrime :: Integral a => a -> Bool | isPrime :: Integral a => a -> Bool | ||

− | isPrime | + | isPrime k = k > 1 && |

− | + | foldr (\p r -> p*p > k || k `rem` p /= 0 && r) | |

− | + | True primesTME | |

− | + | ||

</haskell> | </haskell> | ||

− | + | This uses | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

<haskell> | <haskell> | ||

{-# OPTIONS_GHC -O2 -fno-cse #-} | {-# OPTIONS_GHC -O2 -fno-cse #-} | ||

Line 33: | Line 25: | ||

</haskell> | </haskell> | ||

− | The tree-merging Eratosthenes sieve here seems to strike a good balance between efficiency and brevity | + | The tree-merging Eratosthenes sieve here seems to strike a good balance between efficiency and brevity. More at [[Prime numbers]] haskellwiki page. The semi-standard <code>union</code> function is readily available from <hask>Data.List.Ordered</hask> package, put here just for reference: |

+ | |||

<haskell> | <haskell> | ||

-- duplicates-removing union of two ordered increasing lists | -- duplicates-removing union of two ordered increasing lists | ||

Line 41: | Line 34: | ||

GT -> y : union (x:xs) ys | GT -> y : union (x:xs) ys | ||

</haskell> | </haskell> | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− |

## Revision as of 09:20, 1 June 2011

(**) Determine whether a given integer number is prime.

Well, a natural number *k* is a prime number if it is larger than **1** and no natural number *n >= 2* with *n^2 <= k* is a divisor of *k*. However, we don't actually need to check all natural numbers *n <= sqrt k*. We need only check the * primes p <= sqrt k*:

isPrime :: Integral a => a -> Bool isPrime k = k > 1 && foldr (\p r -> p*p > k || k `rem` p /= 0 && r) True primesTME

This uses

{-# OPTIONS_GHC -O2 -fno-cse #-} -- tree-merging Eratosthenes sieve -- producing infinite list of all prime numbers primesTME = 2 : gaps 3 (join [[p*p,p*p+2*p..] | p <- primes']) where primes' = 3 : gaps 5 (join [[p*p,p*p+2*p..] | p <- primes']) join ((x:xs):t) = x : union xs (join (pairs t)) pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t gaps k xs@(x:t) | k==x = gaps (k+2) t | True = k : gaps (k+2) xs

`union`

function is readily available from Data.List.Ordered

-- duplicates-removing union of two ordered increasing lists union (x:xs) (y:ys) = case (compare x y) of LT -> x : union xs (y:ys) EQ -> x : union xs ys GT -> y : union (x:xs) ys