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.