Write a logical (boolean) function named isPrime(n) that takes in an integer number n, and finds whether it is a Prime number or not. Example output is the following,

isPrime(23)

True

isPrime(12)

False


Note that you do not need and must not use a for-loop for this problem (we have not yet discussed loops in our class!). All of it can be done using recursive function concept.

Hint: To check if a number is a prime number, you would need to check if the number is divisible by any number smaller than itself. However, there is no need to check the divisibility for all numbers smaller than the target number. This divisibility checking can be done only up to a certain number. You may think that this checking should be done up to half the target number. But you can in fact end your search much sooner than reaching the half value. For example, consider the following checks for the number n = 100. When we test all possible divisors up to n/2, we will discover some factors twice. To observe this, rewrite the list of divisors as a list of products, each equal to 100:

$2 \times 50, 4 \times 25, 5 \times 20, 10 \times 10, 20 \times 5, 25 \times 4, 50 \times 2$

Notice that products past $10 \times 10$ merely repeat numbers which appeared in earlier products. Use this example to find the optimal threshold in your search for primality.

Hint: You can verify the accuracy of your MATLAB script via by checking its output against MATLAB’s built-in function isprime().

Here is an example implementation of isPrime.m,

function outLogical = isPrime(n)

divisor = 2;
outLogical = true;
sqrt_n = round(sqrt(n));
outLogical = isDivisible(n,sqrt_n,divisor);

function output = isDivisible(n,sqrt_n,divisor)
if mod(n,divisor) == 0
output = false;
elseif sqrt_n<divisor
output = true;
return
else
divisor = divisor + 1;
output = isDivisible(n,sqrt_n,divisor);
end
end

end

def isPrime(n):

isPrime = True

def is_divisible(n,divisor):
if n<(divisor-1)*divisor: return False
if n%divisor==0: return True
else:
divisor += 1
return is_divisible(n,divisor)

if is_divisible(n,divisor=2): isPrime=False
return isPrime