Algorithms #2 – Is a Prime Number?

The algorithm is necessary for a coding interview for a data scientist and a software engineering job. This article’s topic is one of the most important subjects.

Problem

Write a function to judge if a number is prime, where a prime number is a natural number greater than or equal to 2, whose positive divisor is 1 and itself. The function returns True if the number is prime, or returns False otherwise.

Solution

This solution is a simple approach without any specific mathematical knowledges. The approach consists three steps as follows.

1. Check the special case.
   From the definition of a prime number, 1 is NOT a prime number. And, 2 is the only prime number among even numbers.
2. An even number is NOT a prime number.
3. Judge against odd numbers.
   In turn, we will check the condition if a number exists whose remainder is zero, it is not a prime number. Note that, using prior knowledge that the number is not even, it is sufficient to examine only odd numbers.

def is_prime(num):
    # check the special case,
    # 1 is NOT a prime number,
    # the only prime number 2 in even numbers.
    if num <= 1:
        return False
    elif num == 2:
        return True
    
    # even number is a False case
    if num % 2 == 0:
        return False

    # Only checking on odd numbers is sufficient.
    for i in range(3, num, 2):
        if num % i == 0:
            return False
    return True

Test examples

nums = list(range(2, 15))
for n in nums:
    print(f"{n}: {is_prime(n)}")

>  2: True
>  3: True
>  4: False
>  5: True
>  6: False
>  7: True
>  8: False
>  9: False
>  10: False
>  11: True
>  12: False
>  13: True
>  14: False

As a comment, using mathematical knowledge of integers, it is also possible to implement a solution with a more efficient computational complexity.