3
\$\begingroup\$

For the given below exercise:

Here is one method to check if a number is prime:

def is_prime(n):
    k = 2
    while k < n:
        if n % k == 0:
            return False
        k += 1
    return True

How does this function work?

This is a decent way of testing if a number is prime, but looping k all the way to n might be a bit cumbersome. As a little bonus question, can you think of a better place to stop?

Using the is_prime function, fill in the following procedure, which generates the nth prime number. For example, the 2nd prime number is 3, the 5th prime number is 11, and so on.

def nth_prime(n):

Below is the solution:

def is_prime(n):
    def f(n, k):
        if k > (n // 2):
            return True
        elif n % k == 0:
            return False
        else:
            return f(n, k + 1)
    return f(n, 2)


def nth_prime(n):
    def traverse_for_nth_prime(count, k):
        if count == n:
           return k-1
        elif is_prime(k):
            return traverse_for_nth_prime(count + 1, k + 1)
        else:
            return traverse_for_nth_prime(count, k + 1)
    return traverse_for_nth_prime(0, 2)


print(nth_prime(20))

Above code is written in functional paradigm. Can it be improved, especially in relation to being optimised from recursion depth limit perspective, by strictly following functional paradigm?

\$\endgroup\$
6
\$\begingroup\$

A "functional" method avoiding recusion would be

from itertools import count

def gen_primes():
    return filter(is_prime, count(2))

def nth(n, iterable):
    return next(val for i, val in enumerate(iterable) if i == n)

def nth_prime(n):
    return nth(n, gen_primes())

To prove that this is functional, here's the Haskell:

enumerate = zip [0..]

primes = filter is_prime [2..]

nth iterable n = head [v | (i, v) <- enumerate iterable, i == n]

nth_prime = nth primes

The trick is to make everything as small as logically possible and see how to extract common functionality.

\$\endgroup\$
  • \$\begingroup\$ Beautifully done! +1 \$\endgroup\$ – janos Feb 28 '15 at 15:40
3
\$\begingroup\$

There's no need to check the count in every recursion step. Most of the numbers are not primes, and for sequences of non-primes, count will be unchanged. It's enough to check count after each confirmed prime, like this:

def traverse_for_nth_prime(count, k):
    if is_prime(k):
        if count + 1 == n:
            return k
        else:
            return traverse_for_nth_prime(count + 1, k + 1)
    else:
        return traverse_for_nth_prime(count, k + 1)

In any case, recursion is not well suited to finding primes. Finding the 200th prime is already too much for this method, at least on my computer it reaches the maximum depth of recursion.

A better, more Pythonic way would be to use a generator:

def gen_primes():
    candidate = 2
    while True:
        if is_prime(candidate):
            yield candidate
        candidate += 1


def nth_prime(n):
    i = 0
    for prime in gen_primes():
        i += 1
        if i == n:
            return prime

This will have no problem reaching the 200th prime. It also won't have problem reaching the 300th, but then the is_prime method will reach the maximum depth of recursion.

To reach more and larger prime numbers, you will need to change is_prime to use iteration.

To reach more and larger prime numbers faster, you should use a sieve, for example the Sieve of Eratosthenes.

\$\endgroup\$
  • \$\begingroup\$ When I say, I followed FP, that means I followed this rule of thumb. for example I did not use re-assignment. \$\endgroup\$ – overexchange Feb 28 '15 at 14:31
  • 1
    \$\begingroup\$ @overexchange this is why Python only partly supports FP, as I put it here. You can extend the recursion depth, but only so far. \$\endgroup\$ – jonrsharpe Feb 28 '15 at 14:54
1
\$\begingroup\$

I fully agree with what others have said about generators, sieves, etc.

However, I am surprised that no one has mentioned your line

if k > (n // 2):
    return True

You don't have to test all the way up to n/2; it's enough to test up to sqrt(n). (Why?) Note that a convenient alternative to taking the square root of n is just to square k.

Also, incrementing k by 1 at each step is pretty inefficient: the only even number you have to check is 2, so you can basically double your efficiency if you treat 2 separately and otherwise check only odd k. So fairly small changes to your original code can yield pretty dramatic improvements in efficiency:

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    def f(n,k):
        if k*k > n:
            return True
        elif n % k == 0:
            return False
        else:
            return f(n, k + 2)
    return f(n, 3)

In the same way, you can improve your nth_prime function somewhat:

def nth_prime(n):
    if n == 1:
        return 2
    count = 1
    i = 1 # will be incremented immediately to i=3 inside loop
    while count < n:
        i += 2
        if is_prime(i):
            count += 1
    return i

On my computer, this returned the 100,000th prime successfully:

>>> nth_prime(10**5)
1299709

(Compare with https://oeis.org/A006988)

However, it took my computer about 20 seconds to find this value.

When I asked for the 1 millionth prime, it reached Python's default maximum stack recursion depth and raised a RuntimeError. Of course, I'm not sure I would have been willing to wait for it to finish anyway, even if the depth limit were raised. Again, a better method would be to implement a sieve, but the code for that would be quite different.

\$\endgroup\$
  • \$\begingroup\$ your nth_prime does not use recursion, so why do you see recursion maximum stack issue? I need the solution in functional paradigm by just using higher order functions. first question in this exercise. \$\endgroup\$ – overexchange Mar 1 '15 at 3:04
  • \$\begingroup\$ There is recursion in is_prime, so the stack limit is still an issue. However, you're right that I didn't use the same style in my nth_prime function. My main point with this post was the simple improvements that could be made to the algorithm itself, rather than demonstrating the use of the functional paradigm (which you seem to understand very well). \$\endgroup\$ – mathmandan Mar 1 '15 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.