Subtitles section Play video Print subtitles 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.

B1 prime square root square integer test root Python and Prime Numbers || Python Tutorial || Learn Python Programming 9 0 林宜悉 posted on 2020/03/06 More Share Save Report Video vocabulary