Let us first recall what a prime number is. A prime number is a positive integer greater than 1 such that it has only two divisors (typically 1 and itself). For instance, the divisors of 2 are 1 and 2, and thus 2 is a prime number. The divisors of 3 are 1 and 3 and thus 3 is also a prime number. The divisors of 4 are 1, 2, and 4, and therefore it is not a prime number because it has three factors. In fact, one way to verify that 4 is not prime is to notice that 4 can be expressed as 2 times 2, whereas prime numbers can only be expressed as that number times itself.
Checking if 65 is a prime by systematic enumeration
Let us systematically enumerate factors from 2 and see if they divide our given number 65 evenly. We start at 2 and need to go only till the (approximate) square root of 65. (Why? Think about it.) Of course, if you know that 65 has an exact square root, you already know a factor (its square root!) so you can conclude that it is not a prime.
For instance, in our example, to find if 65 is a prime number we can aim to check for factors from 2 to 8.
Check if 2 is a factor of 65 - false
Check if 3 is a factor of 65 - false
Check if 4 is a factor of 65 - false
Check if 5 is a factor of 65 - true
(We stop as soon as we find a factor because that indicates to us that the number is not a prime number. )
Also as described above, you typically do not need to go all the way to the given number to enumerate factors. We only need to check till the square root.
In our case, thus we learn that 65 is not a prime number.
Checking if 65 is a prime using Python
You can automate the above process by writing a Python program.
If you run this program, you will get:
You can also take advantage of numerous Python libraries that provide in-built capabilities for primality testing.
Checking if 65 is a prime using Python SymPy
SymPy is a powerful symbolic mathematics library that includes various mathematical operations and functions, including primality testing. You can use the isprime() function from the SymPy library in Python to check if our given number 65 is prime. Here's how you can use it:
The output is
as expected. The isprime() function from SymPy returns True if the input number is prime and False if it's not. This function uses efficient algorithms for primality testing, making it a reliable choice when working with prime numbers in Python.
So in conclusion it is very easy to check if a number is prime using pencil and paper, using Python by coding your own function, or using a Python module.
If you liked this example, checkout the following additional problems that will help you get comfortable with the idea of primality checking.
Kodeclik is an online coding academy for kids and teens to learn real world programming. Kids are introduced to coding in a fun and exciting way and are challeged to higher levels with engaging, high quality content.