We earn commission when you buy through affiliate links.
This does not influence our reviews or recommendations.Learn more.
This tutorial will teach you how to write a Python program to peek if anumber is primeor not.
And over the next few minutes, youll learn to come up with the optimal solution to this question.
In this tutorial, youll:
For all this and more, lets get started.
What is a Prime Number?
Lets start by reviewing the basics of prime numbers.
In number theory, a natural numbernsaid to beprimeif it hasexactly two factors:1and the number itself (n).
Recall from your school math: a numberiis said to be a factor of the numbern, ifidividesnevenly.
The following table lists down a few numbers, all their factors, and if theyre prime.
you might loop through all numbers from 2 to n 1 using therange()object in Python.
In Python,range(start, stop, step)returns a range object.
Lets now parse the above function definition.
Next, lets call the function with arguments and verify if the output is correct.
In the output above, you see that 2 and 11 are prime (the function returnsTrue).
And 8 and 9 are not prime (the function returnsFalse).
How to Optimize the Python Function is_prime()
We can do a small optimization here.
Observe the list of factors in the table below.
Well, we can see that the only factor ofnthat is greater thann/2isnitself.
If you dont find a non-trivial factor till n/2, you cant find one beyond n/2 either.
Yes, we can!
Proceed to the next section to determine how to improve the time complexity for prime number testing.
The table below shows the factors of the number 18 occurring in pairs.
You may verify the same for a few more numbers if you like.
Also, note that 18 is approximately 4.24.
The figure below shows the factors of 18 plotted on the number line.
Look at the factors of 36 in the table below.
As 36 is a perfect square, a = b = 6 is one of the factors.
For all other factor pairs (a, b), a < 6 and b > 6 holds.
The above snippet shows how you might plot the curves for n and n for a range of values.
Heres a quick example: 2377 is a prime numberverify this!
Conclusion
And its time for a quick summary.
I hope you understand how to test whether a number is prime in Python.
See you all in another tutorial.
Until then, happy coding!
