Problem

MATLAB

Suppose you want to find the largest prime number that is smaller than a given input value by the user. Write a function named getLargestPrime that does so, using for-loop, break, and MATLAB’s intrinsic function isprime(). Here is a test,

getLargestPrime(123)
ans =
   113
Python

Write a Python function that when executed, asks the user to enter an integer number, then the function gives out the number of prime numbers that are smaller than the input integer number. Here is the answer to this question using only the knowledge of recursive functions and if-blocks,

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 n==2:
        isPrime = True
    elif is_divisible(n,divisor=2):
        isPrime = False
    return isPrime

def getNumPrimes(n):
    if n <= 2:
        return 0
    else:
        return isPrime(n-1) + getNumPrimes(n-1)
getNumPrimes(13)
5

(A) Now rewrite getNumPrimes(n) and the other functions in the above code using for-loop this time. Name the new functions get_prime_for(n) and isPrime_for(n), with for in the names indicating that the functions now use for-loops.

(B) Now compare the performance of the two functions getNumPrimes(n=500) and getNumPrimes_for(n=500) using Jupyter’s or IPython’s %timeit magic function. Which one is faster?

Solution

MATLAB
function integer = getLargestPrime(upper)
    if (upper<1)
        disp('input value cannot be less than 1. Goodbye!')
        return
    end
    for integer = upper:-1:1
        if isprime(integer)
            break
        end
    end
end
Python

(A)

def isPrime_for(x):
    if x > 1:
        n = x // 2
        for i in range(2, n + 1):
            if x % i == 0:
                return False
        return True
    else:
        return False

def getNumPrimes_for(n):
    count = 0
    for i in range(2,n):
        if isPrime(i):
            count += 1
    return count

Here is a test,

getNumPrimes_for(13)
5

(B)

%timeit getNumPrimes(500)
1000 loops, best of 3: 1.32 ms per loop
%timeit getNumPrimes_for(500)
1000 loops, best of 3: 1.69 ms per loop  

Interesting, recursive functions seem to be faster than Python for-loops!

Comments