Problem

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.

MATLAB

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

Solution

MATLAB

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
Python
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

Comments