Increased performance of 2.1

Implemented a faster prime-generator and a primality-check.

1 files 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