Personal tools

99 questions/Solutions/31

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, 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'''
+
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 p = p > 1 &&
+
isPrime k = k > 1 &&
(all ((/= 0).(p `rem`)) $ candidateFactors p)
+
foldr (\p r -> p*p > k || k `rem` p /= 0 && r)
+
True primesTME
candidateFactors p = takeWhile ((<= p).(^2)) [2..]
 
 
</haskell>
 
</haskell>
   
Well, a natural number ''p'' is a prime number if it is larger than '''1''' and no natural number ''n >= 2'' with ''n^2 <= p'' is a divisor of ''p''. That's exactly what is implemented: we take the list of all integral numbers starting with '''2''' as long as their square is at most ''p'' and check that for all these ''n'' there is a non-zero remainder concerning the division of ''p'' by ''n''.
+
This uses
   
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>
 
This uses
 
 
<haskell>
 
<haskell>
 
{-# OPTIONS_GHC -O2 -fno-cse #-}
 
{-# OPTIONS_GHC -O2 -fno-cse #-}
Line 32: Line 25:
 
</haskell>
 
</haskell>
   
The tree-merging Eratosthenes sieve here seems to strike a good balance between efficiency and brevity, and semi-standard <code>union</code> function is readily available from <hask>Data.List.Ordered</hask>&nbsp;package, put here just for reference. More at [[Prime numbers]] haskellwiki page.
+
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>&nbsp;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 40: Line 33:
 
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)
 
True primesTME
 
</haskell>
 
 
This reuses same <code>primesTME</code> list on subsequent invocations, but the <hask>(takeWhile ...)</hask>&nbsp;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