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.
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?