From 4db7b9878869678eb8cd6ce8049f12e4982fa9fc Mon Sep 17 00:00:00 2001
From: Ramakrishnan Muthukrishnan <ram@rkrishnan.org>
Date: Sat, 20 Dec 2014 21:35:20 +0530
Subject: [PATCH] hw4: sieve of sundaram

---
 hw4/hw4.hs | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/hw4/hw4.hs b/hw4/hw4.hs
index 455d8b9..078aab2 100644
--- a/hw4/hw4.hs
+++ b/hw4/hw4.hs
@@ -2,6 +2,8 @@
 
 module Hw4 where
 
+import qualified Data.List as L
+
 -- wholemeal programming
 {- |
 
@@ -81,3 +83,17 @@ xor bs = foldr f False bs
 map' :: (a -> b) -> [a] -> [b]
 map' f = foldr f' []
     where f' x acc = (f x) : acc
+
+-- exercise 5
+-- Sieve of Sundaram
+
+cartProd :: [a] -> [b] -> [(a,b)]
+cartProd xs ys = [(x, y) | x <- xs, y <- ys]
+
+genList :: Integer -> [Integer]
+genList n = [1..n]
+
+sieveSundaram :: Integer -> [Integer]
+sieveSundaram n = map (\x -> (2*x + 1)) $ (L.\\) xs $ L.sort $ f (cartProd xs xs)
+    where xs = genList n
+          f ps =  L.nub $ filter (<= n) $ map (\(i,j) -> i + j + 2*i*j) ps
-- 
2.37.2