reset password
Author Message
rabbott
Posts: 1649
Posted 14:38 Aug 29, 2017 |

As you know, here's one way to generate the primes.

oddsFrom3 = [3, 5 .. ]


primeDivisors n = [d | d <- takeWhile (\x -> x^2 <= n) primes, n `mod` d == 0]


primes = 2 : [n | n <- oddsFrom3, null (primeDivisors n)] 

This may seem confusing because it involves two functions that call each other: primes and primeDivisors. You may wonder why this works at all. Why doesn't it get stuck in an infinite recursive loop? As the Project 1 write-up explains, the call to, say, take 10 primes, finds 2 as the first prime. For the second prime it starts generating values from oddsFrom3. The first value is 3. So we call primeDivisors 3. That function looks for primes whose square is less than or equal to 3. The first element of primes has already been computed. It is 2. But 2^2 is not less than or equal to 3. So takeWhile stops! It doesn't continue looking for the next prime. 

What happens if we drop 2: from the front of the definitions of primes?

primes = [n | n <- oddsFrom3, null (primeDivisors n)] 

That would presumably generate all the primes greater than 2. But if we run that code, we are caught in an infinite recursive loop. Why? The call to take 10 primes starts by looking for the first prime. Since no primes are yet known, it asks whether 3 prime and calls primeDivisors 3. That looks for primes whose square is less than or equal to 3. But now we don't have any primes, not even the first one. So we call primes again, which calls primeDivisors 3, etc. 

One way to fix this is to put 2: in front of primes in the definition of primeDivisors.

primeDivisors n = [d | d <- takeWhile (\x -> x^2 <= n) (2:primes), n `mod` d == 0]

Then takeWhile finds something, namely 2, to cause it to stop when it looks for primeDivisors 3. Once we have found that 3 is a prime, takeWhile will always find a prime whose square is greater than the number whose primeDivisors we are checking. That will cause it to stop looking through primes.

Last edited by rabbott at 18:23 Aug 29, 2017.