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.
- 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.
- An even number is NOT a prime number.
- 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.
