Build a function with this simple algorithm
Photo by Pascal Meier on Unsplash
Prime numbers?they bring back memories of secondary school, sitting at my desk crunching through each possible division.
For those who may be unfamiliar, prime numbers are natural numbers (counting numbers) greater than 1 that cannot be produced by multiplying two smaller numbers.
In other words, prime numbers are wholly divisible only by 1 and themselves.
Quick math check, out of the following numbers?1, 2, 3, 4, 5?2, 3, and 5 are prime numbers. The number 1 is not greater than 1 and the number 4 can be produced by multiplying 2×2.
So, how do we programmatically determine if a number is prime?
We need to check that the number meets all our criteria:
- Whole.
- Greater than 1.
- Cannot be evenly divided by any number other than itself and 1.
The Algorithm
Let?s start by solving this for a set value, which will be stored in a variable n and assume that our value is prime. This means we?ll be trying to disqualify it in our algorithm.
n = 5isPrime = True
Next, we need to check if the value is both greater than 1 and is a whole number.
if n <= 1 or n % 1 > 0: isPrime = False
If you?re not familiar with the modulus operator %, check out my article on this handy arithmetic operator.
Assuming we pass this check, the next step is to iterate through the range of values between 1 and n to see if we find an even division.
for i in range(2, n-1): if n % i == 0: isPrime = False
The range() function takes two parameters, our start and stop values, and returns each number between while the for loop will iterate over each value returned from range.
We can make a small improvement to our loop?s efficiency by only iterating to n / 2 as the maximum bound. This is because any whole division we see greater than half of n would have been found as the complementary value is less than half of n.
Since range() requires integer values, we use integer division // to divide n by 2. Here?s the entire algorithm.
Converting Our Algorithm to a Function
Now, we don?t want to copy/paste this algorithm every time it?s needed, so it?s time to create a function. Our function will return either True or False depending on whether the passed value is prime or not.
Do you have a different way of determining if a number is prime? Have you needed to use prime numbers outside of a classroom? Share your thoughts and feedback below!
