Intermediate results in a recursive function

Question

I'm trying to write a function which will find all prime numbers from 2 to 100. I can do so by testing if a number is prime by looking at remainder when the number n is divided by all numbers in 2..n-1.

I would however like only to test against prime numbers I have already found. This is how far I got writing my recursive function, but I don't know how to replace [2..t-1] with the prime numbers I have already worked out (the intermediate result of my recursive function I guess). How can I do that?

primes = go [2..100]
    where
        go l@(t:ts)
            | all (\x -> t `rem` x /= 0) [2..t-1] = t:(go ts)
            | otherwise = go ts
        go [] = []

main = print primes

Answer 1

Here's one possible way:

primes = 2 : go [3..]
    where
        go (t:ts)
            | all (\x -> t `rem` x /= 0) (takeWhile (\x->x*x<=t) primes)  = t:(go ts)
            | otherwise = go ts

Here we use the already-calculated part of primes up to the square root of t. Note that we need not to specify the upper bound in primes, it will simply produce an infinite list that you can later chop:

print $ take 1000 primes

Note also that we need to bootstrap primes such that the very first prime is not calculated from previous primes, so that takeWhile could work.