I was given 2 different algorithms written in Haskell aimed to generate the first k primes. As the title suggests, they are the Sieve of Eratoshenes and Euler.
I am trying to understand why Euler implementation uses so much memory. What I thought so far is that the number of streams generated explodes quickly saturating the memory but from what I have understood they should be equal to 2k - 1 where k is the index of the prime we want. So there should be other major problems.
I tried running the code via GHC's Debugger and it shows that much of the memory allocated is from the minus function so I think streams are definitely part of the problem.
Here minus removes from tcs every multiple of p starting from p*p which is coprime to every prime found so far (except p) and finally generates a new stream passed to the next recursive call of eulerSieve.
minus :: [Int] -> [Int] -> [Int]
minus xs@(x:txs) ys@(y:tys)
| x < y = x : minus txs ys
| otherwise = minus txs tys
eulerSieve :: [Int] -> [Int]
eulerSieve cs@(p:tcs) = p:eulerSieve (minus tcs (map (p*) cs))
Reading here I found that the space is bounded by O(k^2) but it doesn't explain why accurately. Any suggestion would be appreciated.