From 96e23eedb94c95b2758db0733f8bb5d823908b87 Mon Sep 17 00:00:00 2001
From: Matthias Wisniowski <matthias.wisniowski@gmail.com>
Date: Mon, 26 Mar 2012 15:17:27 +0200
Subject: Increased performance of 2.1

Implemented a faster prime-generator and a primality-check.
---
 AufgabeFFP2.hs | 31 +++++++++++++++++--------------
 1 file changed, 17 insertions(+), 14 deletions(-)

diff --git a/AufgabeFFP2.hs b/AufgabeFFP2.hs
index 7993c01..44b2efb 100644
--- a/AufgabeFFP2.hs
+++ b/AufgabeFFP2.hs
@@ -3,23 +3,26 @@ where
 
 -- 1
 
+-- primality check
+isPrime :: Integer -> Bool
+isPrime n = n > 1 &&
+	foldr (\p r -> 
+		p*p > n 
+		|| (
+			(n `mod` p) /= 0 
+			&& r
+		)
+	)
+	True primes
+	
+-- series of primes
 primes :: [Integer]
-primes = sieve [2 ..]
-
--- sieve of eratosthenes (according to lecture slides)
-sieve :: [Integer] -> [Integer]
-sieve (x:xs) = x : sieve [ y | y <- xs, mod y x > 0]
+primes = 2:filter isPrime [3,5..]
 
 -- generate all pairs with map and then filter only the valid ones
--- TODO: filtering should be optimized, still a bit slow
+-- pair is valid if the second component n is a prime
 pps :: [(Integer, Integer)]
-pps = filter validPair $ map (\x -> (x,x+2)) primes
-	where
-		-- pair is valid if the second component n is a prime
-		-- since simply checking if the Integer is element of the prime-list 
-		-- does not terminate for non-primes, we take the first n primes
-		validPair :: (Integer,Integer) -> Bool
-		validPair (_,maybePrime) = elem maybePrime $ take (fromInteger maybePrime) primes
+pps = filter (\(_,y) -> isPrime y) $ map (\x -> (x,x+2)) primes
 				
 -------------------------------------------------------------------------------
 
@@ -27,7 +30,7 @@ pps = filter validPair $ map (\x -> (x,x+2)) primes
 
 -- generates powers of 2	
 pof2s :: [Integer]
-pof2s = [1] ++ (map (2*) pof2s)
+pof2s = [1] ++ map (2*) pof2s
 	
 pow :: Int -> Integer
 pow 0 = 1
-- 
cgit v1.2.3