Difference between revisions of "99 questions/Solutions/31"
< 99 questions | Solutions
Jump to navigation
Jump to search
(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. |
||
| ⚫ | |||
| − | '''Solution 1''' |
||
<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) |
|
| ⚫ | |||
| − | |||
| − | candidateFactors p = takeWhile ((<= p).(^2)) [2..] |
||
</haskell> |
</haskell> |
||
| ⚫ | |||
| ⚫ | Well, a natural number '' |
||
| − | However, we don't actually need to check all natural numbers ''<= sqrt P''. We need only check the '''''primes''' <= sqrt P'': |
||
| − | |||
| − | <haskell> |
||
| − | candidateFactors p = let z = floor $ sqrt $ fromIntegral p + 1 in |
||
| − | takeWhile (<= z) primesTME |
||
| − | </haskell> |
||
| ⚫ | |||
<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> |
||
| − | '''Solution 2''' |
||
| − | |||
| − | The following is faster (in Hugs, Nov 2002 version): |
||
| − | <haskell> |
||
| − | isPrime n = n > 1 && |
||
| − | foldr (\p r -> p*p > n || n `rem` p /= 0 && r) |
||
| ⚫ | |||
| − | </haskell> |
||
| − | |||
| − | This reuses same <code>primesTME</code> list on subsequent invocations, but the <hask>(takeWhile ...)</hask> list in the first solution seems to be recreated anew for each call to <code>isPrime</code> (i.e. it may or may not be eliminated by a compiler, while the second solution explicitly uses the same <code>primesTME</code> list so there's no problem to begin with). |
||
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
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 union function is readily available from Data.List.Ordered package, put here just for reference:
-- 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