-- $Id: Aufgabe3.hs,v 1.8 2003/11/26 07:27:46 fp010 Exp $
module Aufgabe3(isPrime,listPrime,primFaktorZerlegung,kgv) where

----------------------------------------------------------------------------
isPrime :: Integer -> Bool
allPrimes :: [Integer]

-- note: quotRem is faster than divMod in hugs!

{- straightforward but slow
isPrime n = (factors n == []) && n >= 2
    where factors n = [ x | x <- [2..n-1], n `rem` x == 0 ]

allPrimes = [ x | x <- [1..], isPrime x ]
-}

-- needs memory to hold lower primes but more efficient for regular
-- lookups
allPrimes = sieb [2..] where
  sieb (p:x) = p : sieb [ n | n <- x, rem n p > 0 ]

-- actually the non-commented functions below would work as well, even
-- if we defined instead:
--
-- allPrimes = [2..]
--
-- For one-shot calls this would be actually more efficient, but when
-- iterating over allPrimes more than once (e.g. in listPrimes), it
-- pays off to have cached previously calculated primes...

-- the lookup... note the termination at sqrt(n), which means that we
-- need allPrimes to be evaluated only up to that point, and not
-- all the way up to n.
isPrime n | n > 1 = isP n allPrimes 
	  | n < 0 = isPrime (-n)
          | otherwise = False
 where
  isP n (p:ps) | p^2 > n        = True
	       | n `rem` p == 0 = False
	       | otherwise      = isP n ps

----------------------------------------------------------------------------
listPrime :: Integer -> Integer -> [Integer]

{- straightforward but inefficient for large ranges with large numbers
-- see below for explaination

listPrime a b = (upto b (from a allPrimes)) where
  from a ap@(p:ps) | a > p     = from a ps
		   | otherwise = ap
  upto b (p:ps) | b >= p     = p:(upto b ps)
		| otherwise = []

-- actually the above can be written with prelude helpers as

listPrime a b = takeWhile (<=b) (dropWhile (a>) allPrimes)

-}

-- the following variant is _much_ faster on one-shot calls; the reason
-- is, we don't have to build all primes up to b, but only all up to
-- sqrt(b)!  but then isPrime has to re-iterate allPrimes up to the
-- first divisor for each element in [a..b], which is why listPrime is
-- much faster, once we have built up allPrimes up to b;

listPrime a b = filter isPrime [a..b]

{- filter is implemented by list-comprehension, we could have
-- written the above as well as

listPrime a b = [ x | x <- [a..b], isPrime x ]

-}

----------------------------------------------------------------------------
primFaktorZerlegung :: Integer -> [(Integer,Integer)]

primFaktorZerlegung n | n < 0 = (-1,1):primFaktorZerlegung (- n)
		      | n == 0 = undefined
		      | otherwise = compress (pfz n allPrimes) 
 where
  pfz n ps@(p:pleft) | n < 2   = []
		     | n < p^2 = [n] -- see isPrime
		     | n > 1   = let (n',r) = quotRem n p in 
				   if r == 0 then p:(pfz n' ps) 
				             else pfz n pleft

  compress (x:xs) = compress' 1 x xs where
    compress' n y (x:xs) | y == x    = compress' (n + 1) y xs
	  	         | otherwise = (y,n) : (compress' 1 x xs)
    compress' n y [] = [(y,n)]
  compress [] = []

----------------------------------------------------------------------------
kgv :: Integer -> Integer -> Integer

-- bold solution:
-- kgv = lcm

-- ...using ggt from Aufgabe1.lhs (or simply Prelude.gcm...)
-- kgv _ 0         = 0
-- kgv 0 _         = 0
-- kgv x y         = abs ((x `quot` Aufgabe1.ggt x y) * y)

-- multimengen variante mit @-abuse - nicht besonders flott... ;-)
kgv a b = pFJoin (munion (pfz a) (pfz b)) where
  pfz = primFaktorZerlegung
  pFJoin z = abs (product (map (uncurry (^)) z))
  munion as@(a@(p1,n1):p1s) bs@((p2,n2):p2s) | p1 == p2 = (p1,n1 `max` n2):(munion p1s p2s)
					     | p1 < p2 = a:(munion p1s bs)
					     | otherwise = munion bs as
  munion [] b = b
  munion a [] = a

----------------------------------------------------------------------------
-- $Log: Aufgabe3.hs,v $
-- Revision 1.8  2003/11/26 07:27:46  fp010
-- added some comments
--
-- Revision 1.7  2003/11/16 15:08:22  fp010
-- improved worst case (argument is large prime) for primFaktorZerlegung
--
-- Revision 1.6  2003/11/15 22:58:57  fp010
-- added some more comments
--
-- Revision 1.5  2003/11/15 13:16:50  fp010
-- added note about curiously faster listPrime variant
--
-- Revision 1.4  2003/11/15 12:57:27  fp010
-- added lookup-based listPrime implementation; improved primFaktorZerlegung to handle negative input range as well; make isPrime properly handle negative values;
-- make kgv return reasonable values for negative arguments; made use of quotRem where divMod was used;
--
-- Revision 1.3  2003/11/15 12:30:18  fp010
-- added a lookup-based isPrime implementation
--
-- Revision 1.2  2003/11/13 17:49:52  fp010
-- added pfz-based kgv solution
--
-- Revision 1.1  2003/11/12 21:10:18  fp010
-- checked in first draft
--
--