Prime numbers are important creatures. They are the building blocks of the
whole numbers, and are central to the field known as Number Theory. Primes
are also a key ingredient in some cryptographic methods, like the RSA
algorithm. But identifying prime numbers is difficult.
Today, we rise to the challenge and will use Python to write a series of
functions to check if an integer is prime. I hope you're ready for the main
event, because it's prime time.
To begin, let's recall the definition of a prime number.
A prime number is a positive integer that is divisible only by itself
and 1. If an integer can be factored into smaller numbers, we call it a composite
number. And the integer 1 is neither prime nor composite. It's called the unit.
For our first version of the function, we will check all divisors from 2 through
n minus 1. We skip 1 and n since every number is divisible by itself and 1. Let's call
the function is prime V 1. And the input will be our integer. First do the right
thing, and write a brief docstring describing this function. Next, loop over
all numbers from 2 through n minus 1. Remember, with the range function the
last number is not included. 2 see if d divides n evenly, we'll use the percent
operator. This gives you the remainder when you divide n by D. If we get a
remainder of 0, then n has a divisor other than itself and 1, so it is not prime.
But if at the end of the loop we have not found a divisor, then n must be prime,
so return true. Let's test this on the first 20 positive integers.
Our function works. It correctly identifies the prime numbers. But how fast is this
function? Let's find out by doing a larger test. We'll compute the time
required to test the integers up to 100,000. To do so, import the time module
and call the time function before and after the loop. We won't print out
anything, because we're interested in the computation speed, not how fast our
system can print text.
I'm... disappointed.
I think we can do better.
To improve our function, we will
use a trick to reduce the number of divisors in the for loop.
To see the trick let's look at all the ways we can factor 36 as the product of two positive
integers. We'll arrange the product so the first factor is always increasing,
while the second factor is always decreasing.
36 is a perfect square, since
it's equal to six times six. Notice that the factorizations after
this are the same as the factorizations before it, just in reverse order. If the
number is not a perfect square, that's okay. To see why, look at 18. Here, there
are six products and the first three and the last three are the same, just in
reverse order. But the product of the square root of 18 times the square root
of 18 still provides a dividing line between duplicate products. For any
positive integer n, the same thing happens. This means to test for divisors,
you only have to test the integers up to the square root of n. Let's use this to
improve our algorithm.
For our second version, we will only test divisors from
2 up to the square root of N. In the event the square root is not a whole
number, we'll just round down. Since we'll be taking square roots we need to import
the math module.
To find the largest possible divisor we'll test, take the
square root of n then round down using the floor function. Since we want to be
sure to test this number we have to add one to the range function
Let's check that the function works.
It does. Let's see if it's faster than the first .
Once again, we'll compute the time required to test the integers
up to 100,000
This is much much better.
But I suspect there is still room for improvement.
In our loop, we go over all even integers up to the limit.
This is a waste. If the input is even and bigger than 2, we will find a divisor on
the first step. But if the input is odd, it's a waste to check the even divisors.
Let's fix this in version 3 of our function.
The first thing we will do is check if n is even.
We only do this for integers larger than 2, since 2 is a
prime number. If the input is larger than 2 and even then it cannot be prime.
Next, when we range over the possible divisors, we will add a third parameter:
a step value.
This range will start at 3, and cover all odd numbers up to our limit.
This should eliminate roughly half of all division operations.
Let's now test and time this function.
The test looks good. But how fast is it?
roughly twice as fast as version two.
I'm feeling some kind of emotion
Could it be joy?
With just a few simple optimizations, we were able to see dramatic improvements
in performance in our prime testing function. But what if you are working
with extremely large integers? If you are building or cracking codes, these
functions aren't nearly fast enough. You will need to go deeper.
After you subscribe to our channel, I would encourage you to look into the subject
of pseudo primes. In your excitement, you may feel the need to visit our Patreon page.
Don't worry. This is a completely normal reaction to one of our videos.