Hướng dẫn is prime number python
Example to check whether an integer is a prime number or not using for loop and if...else statement. If the number is not prime, it's explained in output why it is not a prime number. Show
To understand this example, you should have the knowledge of the following Python programming topics:
A positive integer greater than 1 which has no other factors except 1 and the number itself is called a prime number. 2, 3, 5,
7 etc. are prime numbers as they do not have any other factors. But 6 is not prime (it is composite) since, Example 1: Using a flag variable
In this program, we have checked if num is prime or not. Numbers less than or equal to 1 are not prime numbers. Hence, we only proceed if the num is greater than 1. We check if num is exactly divisible by any number from Outside the loop, we check if
Note: We can improve our program by decreasing the range of numbers where we look for factors. In the above program, our search range is from 2 to We could have used the
range, You can change the value of variable num in the above source code to check whether a number is prime or not for other integers. In Python, we can also use the Example 2: Using a for...else statement
Output 407 is not a prime number 11 times 37 is 407 Here, we have used a It works on the logic that the So, in the This tutorial will teach you how to write a Python program to check if a number is prime or not. If you’ve ever taken up coding tests, you’ll have come across the math question on the test for primality or to check if a number is prime. And over the next few minutes, you’ll learn to come up with the optimal solution to this question. In this tutorial, you’ll:
For all this and more, let’s get started. What is a Prime Number?Let’s start by reviewing the basics of prime numbers.
The following table lists down a few numbers, all their factors, and if they’re prime.
From the above table, we can write down the following:
So 1 and n are trivial factors for any number n. And a prime number should not have any factors other than these two. This means that when you go from 2 to n – 1, you should not be able to find a non-trivial factor that divides n without a remainder. O(n) Algorithm to Check if a Number is Prime in PythonIn this section, let us formalize the above approach into a Python function. You can loop through all numbers from 2 to n – 1 using the
Since we need the set of integers from 2 to n-1, we can specify Here’s what we would like to do:
Python Function to Check for Prime NumberUsing the above, we can go ahead and define the function
Let’s now parse the above function definition.
Next, let’s 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 returns How to Optimize the Python Function is_prime()We can do a small optimization here. Observe the list of factors in the table below.
So this means you don’t have to loop all the way up to n – 1. You can instead run the loop only up to n/2. If you don’t find a non-trivial factor till n/2, you can’t find one beyond n/2 either. Now let’s modify the function
Let’s go ahead and verify the output through a few function calls.
Even though it may seem like we have optimized, this algorithm is not more efficient than the previous one in terms of runtime complexity. In fact, both of them have O(n) runtime complexity: proportional to the value of n or linear in n. Can we do better? Yes, we can! ▶️ Proceed to the next section to determine how to improve the time complexity for prime number testing. O(√n) Algorithm to Check for Prime Number in PythonIt happens that the factors of a number occur in pairs.
Let’s verify this through an example. 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. And in the factors that occur in pairs (a, b), you can see that if a is less than 4.24, then b is greater than 4.24—in this example, (2, 18) and (3, 6).
The figure below shows the factors of 18 plotted on the number line. If the number n happens to be a perfect square, you’ll have a = b = √n as one of the factors. ▶️ 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.
Summing up, we have the following:
So instead of looping through all integers up to n/2, you may choose to run up to √n. And this is a lot more efficient than our previous approach. How to Modify is_prime() to O(√n) AlgorithmLet’s proceed to optimize the function to check for prime numbers in Python.
Now, let’s parse the above function definition:
The code cell below verifies that our function
In the next section, let us create a few simple plots to understand O(n) and O(√n) visually. Comparing O(n) and O(√n) Visually▶️ Run the following code snippet in a Jupyter notebook environment of your choice.
The above snippet shows how you can plot the curves for n and √n for a range of values.
From the plot below, we see that √n is significantly smaller than n. Let us now increase the range to as high as 2000 and repeat the same steps as above.
From the above plot, you can infer that O(√n) algorithm is significantly faster when you’re testing if a large number is prime. Here’s a quick example: 2377 is a prime number—verify this!😀 While the O(n) approach will take the order of 2000 steps, the O(√n) algorithm can help arrive at the answer in just 49 steps.✅ Conclusion⏳ And it’s time for a quick summary.
I hope you understand how to check if a number is prime in Python. As a next step, you may check out our tutorial on Python programs on string operations—where you’ll learn to check if strings are palindromes, anagrams, and more. See you all in another tutorial. Until then, happy coding!👩🏽💻 |