Check if number is simple python

How to Check if a Number is Prime in Python

Invicti Web Application Security Scanner – the only solution that delivers automatic verification of vulnerabilities with Proof-Based Scanning™.

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.

• review the basics of prime numbers,
• write Python code to check if a number is prime, and
• optimize it further to get an O(√n) runtime algorithm.

For all this and more, let’s get started.

What is a Prime Number?

Let’s start by reviewing the basics of prime numbers.

In number theory, a natural number n said to be prime if it has exactly two factors: 1 and the number itself (n). Recall from your school math: a number i is said to be a factor of the number n, if i divides n evenly. ✅

The following table lists down a few numbers, all their factors, and if they’re prime.

n	Factors	Is Prime?
1	1	No
2	1, 2	Yes
3	1, 3	Yes
4	1, 2, 4	No
7	1, 7	Yes
15	1, 3, 5, 15	No

From the above table, we can write down the following:

• 2 is the smallest prime number.
• 1 is a factor of every number.
• Every number n is a factor of itself.

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 Python

In 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 range() object in Python.

In Python, range(start, stop, step) returns a range object. You can then iterate over the range object to get a sequence from start all the way up to stop -1 in steps of step .

Since we need the set of integers from 2 to n-1, we can specify range(2, n) and use it in conjunction with for loop.

Here’s what we would like to do:

• If you find a number that divides n evenly without a remainder, you can immediately conclude that the number is not prime.

• If you’ve looped through the entire range of numbers from 2 all the way up to n – 1 without finding a number that divides n evenly, then the number is prime.

Python Function to Check for Prime Number

Using the above, we can go ahead and define the function is_prime() as follows.

def is_prime(n): for i in range(2,n): if (n%i) == 0: return False return True

Let’s now parse the above function definition.

• The above function is_prime() takes in a positive integer n as the argument.
• If you find a factor in the specified range of (2, n-1), the function returns False —as the number is not prime.
• And it returns True if you traverse the entire loop without finding a factor.

Next, let’s call the function with arguments and verify if the output is correct.

is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True

In the output above, you see that 2 and 11 are prime (the function returns True ). And 8 and 9 are not prime (the function returns False ).

How to Optimize the Python Function is_prime()

We can do a small optimization here. Observe the list of factors in the table below.

Number	Factors
6	1, 2, 3 , 6
10	1, 2, 5 , 10
18	1, 2, 3, 6, 9 , 18

Well, we can see that the only factor of n that is greater than n/2 is n itself.

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 is_prime() to check for factors in the range (2, n/2)

def is_prime(n): for i in range(2,int(n/2)): if (n%i) == 0: return False return True

Let’s go ahead and verify the output through a few function calls.

is_prime(9) # False is_prime(11) # True

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 Python

It happens that the factors of a number occur in pairs.

If a is a factor of the number n, then there also exists a factor b such that a x b = n, or simply, ab = n.

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).

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.

Let us now increase the range to as high as 2000 and repeat the same steps as above.

import numpy as np import seaborn as sns import pandas as pd n = 2000 x = np.arange(n) y1 = np.sqrt(x) y2 = x df = pd.DataFrame() sns.set_theme() sns.lineplot(data = df) 

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.

• To check if a number is prime, the naïve approach is to loop through all numbers in the range (2, n-1). If you don’t find a factor that divides n, then n is prime.
• As the only factor of n greater than n/2 is n itself, you may choose to run only up to n/2.
• Both of the above approaches have a time complexity of O(n).
• As factors of a number occur in pairs, you can run only up to √n. This algorithm is a lot faster than O(n). And the gain is appreciable when checking if a large number is prime or not.

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!👩🏽‍💻

Источник

6 Best Ways To Check If Number Is Prime In Python

This article will learn how to check if a number is prime or not in Python. Usually, we all know some common methods using library functions or without using library functions. But how many of us know that there are 6 ways to check a prime number. Maybe some of us will be familiar with some methods. But this article will teach you all the possible ways. Let us move on to check if a number is prime or not.

In the number system, we have two types of numbers. They are Prime and composite. Prime numbers are the numbers that are not the product of any other numbers. These numbers are always natural numbers. For example, 13 is a prime number. Because we cannot get this number as a product of any other two numbers except to the product of 1, on the other hand, if we take 4, it will show a result as a composite because it is a product of 2X2. I hope now all are clear about prime numbers.

The following methods are available:

6 Ways To Check If a Number Is Prime in Python

1: Using isprime()

Example:

def isprime(num): for n in range(2,int(num**0.5)+1): if num%n==0: return False return True print(isprime(7)) print(isprime(8))

This method is implemented using function. It will return True if the number is prime. Otherwise, it will return False. First checking with 7 and then with 8.

Example:

def isprime(num): if num==2 or num==3: return True if num%2==0 or num
This method is implemented using function. It will return True if the number is prime. Otherwise, it will return False. First checking with 13 and then with 18.
Example:
def isprime(num): if num == 2 or num == 3: return True if num < 2 or num%2 == 0: return False if num < 9: return True if num%3 == 0: return False a = int(num**0.5) b = 5 while b 
This method is implemented using function. It will return True if the number is prime. Otherwise, it will return False. First checking with 15 and then with 2.
Example:
def isprime(num): if num> 1: for n in range(2,num): if (num % n) == 0: return False return True else: return False print(isprime(64)) print(isprime(5))
 
This method is implemented using function. It will return True if the number is prime. Otherwise, it will return False—first checking with 64 and then with 5.
 
2: Using if-else statements
 
n=int(input("Enter a number:")) if n>1: for i in range(2,n//2): if(n%i)==0: print(n,"is not a prime number") break else: print(n,"is a prime number") else: print(n,"is neither prime nor composite")
 
This code is normally using loops. Here we are getting a number as an input from the user. It performs the code and gives the result to the user. If the user gives 1 as an input, it will display neither prime nor composite.
 
Enter a number:14 14 is not a prime number Enter a number:3 3 is a prime number Enter a number:1 1 is neither prime nor composite
 
3: Using math function to check if number is prime python
 
Math is a module that is already available in the python library. This module contains a lot of mathematical functions. To access this module, we have to import the module as:
 
Here we are using math.sqrt to check if the number is prime or not. sqrt() is a built-in function in python.
 
Syntax
 
Parameter
 
x – that can be any value.
 
Returns
 
It returns the square root of the x value.
 
Code
 
import math def isprime(num): a=2 while a1 print(isprime(14)) print(isprime(7))
 
4: Using sympy module
 
Sympy is a module in the python library. It only depends on mpmath. Here we are simply using a sympy module. The pip command line to install the module is:
 
Syntax
 
Parameter
 
Returns
 
Example:
 
import sympy print(sympy.isprime(90))
 
Example:
 
from sympy import * print(isprime(19))
 
Example:
 
import sympy.ntheory as nt print(nt.isprime(8))
 
5: Using primePy library to check if a number is prime or not
 
The primePy is a library that is useful to perform the operations regarding prime numbers. Here we are using primePy to check whether a number is prime or not. The pip command to install the primePy module:
 
Syntax
 
Parameter
 
Returns
 
Code
 
from primePy import primes print(primes.check(63))
 
6: Using is_integer function
 
 is_integer is a built-in function that is useful to check if the given number is an integer or not. It is also useful to check if it is prime or not.
 
Syntax
 
Parameter
 
Returns
 
Boolean values (True or False)
 
Example:
 
def prime(num): a=[] for i in range (1, num+1): if (num/i).is_integer(): a.append(i) if len(a)==2: print("Prime") else: print("Not Prime") prime(2)
 
Learn Something New: How to generate a random prime number?
 
import random def range_primes(a, b): prime = [] for i in range(a, b): is_prime = True for n in range(2, i): if i % n == 0: is_prime = False if is_prime: prime.append(i) return prime prime= range_primes(1,100) random_prime = random.choice(prime) print("Random Prime Number is:", random_prime)
 
Random Prime Number is: 11
 
Check if Number is Prime Using Recursion
 
You can check for all prime numbers using the Prime function. Simply pass the number as th3 argument.
 
i=2 def Prime(no, i): if no == i: return True elif no % i == 0: return False return Prime(no, i + 1)
 
Here, we will recursively call the Prime function to check if the number is prime.
 
FAQs Related to Check If a Number is Prime or Not in Python
 
Prime numbers are the numbers that are not the product of any other numbers. These numbers are always natural numbers.
 
To check if a number is prime or not. We have to create a for loop to iterate the numbers. Suppose the number is greater than one. It will check whether a number is a product of any number. If it is, it displays False as a result.
 
Conclusion
 
Here we have briefly learned about how to check if a number is prime or not. We have learned many possible ways. With that, we also saw how to generate a prime number. We hope this article is helpful. Try to solve the programs on your own to gain more knowledge.
 
Источник