This instructional will educate you ways to write a Python program to take a look at if a **quantity is high** or now not.

If you’ve ever taken up coding checks, you’ll have come around the math query at the check for primality or to take a look at if a quantity is high. And over the following few mins, you’ll be told to get a hold of the optimum resolution to this query.

In this instructional, you’ll:

- overview the fundamentals of high numbers,
- write Python code to take a look at if a quantity is high, and
- optimize it additional to get an O(√n) runtime set of rules.

For all this and extra, let’s get began.

## What is a Prime Number?

Let’s get started by way of reviewing the fundamentals of high numbers.

In quantity concept, a herbal quantity

nstated to beprimeif it hasprecisely two elements:1and the quantity itself (n). Recall out of your college math: a quantityiis stated to be a issue of the quantityn, ifidividesnfrivolously. ✅

The following desk lists down a few numbers, all their elements, and if they’re high.

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 desk, we will write down the next:

- 2 is the smallest high quantity.
- 1 is a issue of each and every quantity.
- Every quantity
`n`

is a issue of itself.

So 1 and n are trivial elements for any quantity n. And a high quantity shouldn’t have any elements as opposed to those two.

This signifies that whilst you move from 2 to n – 1, you will have to *now not* be ready to in finding a non-trivial issue that divides n with out a the rest.

## O(n) Algorithm to Check if a Number is Prime in Python

In this phase, allow us to formalize the above method into a Python serve as.

You can loop via all numbers from 2 to n – 1 the use of the `vary()`

object in Python.

In Python,

`vary(get started, forestall, step)`

returns a vary object. You can then iterate over the variability object to get a collection from`get started`

the entire method up to`forestall -1`

in steps of`step`

.

Since we want the set of integers from 2 to n-1, we will specify `vary(2, n)`

and use it in conjunction with `for`

loop.

Here’s what we would really like to do:

- If you in finding a quantity that divides
**n**frivolously with out a the rest, you’ll be able to straight away conclude that the quantity is now not high.

- If you’ve looped via all the vary of numbers from
**2**the entire method up to**n – 1**with out discovering a quantity that divides**n**frivolously, then the quantity is high.

## Python Function to Check for Prime Number

Using the above, we will move forward and outline the serve as `is_prime()`

as follows.

```
def is_prime(n):
for i in vary(2,n):
if (npercenti) == 0:
go back False
go back True
```

Let’s now parse the above serve as definition.

- The above serve as
`is_prime()`

takes in a certain integer**n**because the argument. - If you in finding a issue in the desired vary of (2, n-1), the serve as returns
`False`

—because the quantity is now not high. - And it returns
`True`

if you traverse all the loop with out discovering a issue.

Next, let’s name the serve as with arguments and check if the output is proper.

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

In the output above, you notice that 2 and 11 are high (the serve as returns `True`

). And 8 and 9 don’t seem to be high (the serve as returns `False`

).

## How to Optimize the Python Function is_prime()

We can do a small optimization right here. Observe the listing of things in the desk underneath.

Number |
Factors |

6 | 1, 2, 3, 6 |

10 | 1, 2, 5, 10 |

18 | 1, 2, 3, 6, 9, 18 |

Well, we will see that the one issue of

nthat is more thann/2isnitself.

So this implies you don’t have to loop the entire method up to n – 1. You can as an alternative run the loop handiest up to n/2.

If you don’t in finding a non-trivial issue until n/2, you’ll be able to’t in finding one past n/2 both.

Now let’s adjust the serve as `is_prime()`

to take a look at for elements in the variability (2, n/2)

```
def is_prime(n):
for i in vary(2,int(n/2)):
if (npercenti) == 0:
go back False
go back True
```

Let’s move forward and check the output via a few serve as calls.

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

Even although it will appear to be we have now optimized, this set of rules is now not extra environment friendly than the former one in phrases of runtime complexity. In truth, either one of them have **O(n)** runtime complexity: proportional to the worth of n or linear in n.

Can we do higher? Yes, we will!

▶️ Proceed to the following phase to resolve how to support the time complexity for top quantity checking out.

## O(√n) Algorithm to Check for Prime Number in Python

It occurs that the criteria of a quantity happen in pairs.

If

ais a issue of the quantityn, then there additionally exists a issuebsuch thata x b = n, or just,ab = n.

Let’s check this via an instance.

The desk underneath presentations the criteria of the quantity 18 happening in pairs. You might check the similar for a few extra numbers if you favor.

Also, word that √18 is roughly 4.24.

And in the criteria that happen in pairs **(a, b)**, you’ll be able to see that if **a** is lower than 4.24, then **b** is more than 4.24—in this case, (2, 18) and (3, 6).

The determine underneath presentations the criteria of 18 plotted at the quantity line.

If the quantity n occurs to be a best sq., you’ll have a = b = √n as one of the crucial elements.

▶️ Look on the elements of 36 in the desk underneath. As 36 is a best sq., a = b = 6 is one of the crucial elements. For all different issue pairs (a, b), a < 6 and b > 6 holds.

Summing up, we have now the next:

- Every quantity
**n**will also be written as**n = a x b** - If
**n**is a best sq., then**a = b = √n**. - And if
**a < b**, then,**a < √n**and**b > √n**. - Else, if
**a > b**, then**a > √n**and**b < √n**.

So as an alternative of looping via all integers up to n/2, you might make a selection to run up to √n. And this is a lot extra environment friendly than our earlier method.

### How to Modify is_prime() to O(√n) Algorithm

Let’s continue to optimize the serve as to take a look at for top numbers in Python.

```
import math
def is_prime(n):
for i in vary(2,int(math.sqrt(n))+1):
if (npercenti) == 0:
go back False
go back True
```

Now, let’s parse the above serve as definition:

- To compute the sq. root of a quantity, let’s import Python’s built-in math module, and use
`math.sqrt()`

serve as. - As
**n**might not be a best sq., we’ll have to forged it into an integer. use`int(var)`

to forged`var`

into an`int`

. - To be certain we’re in truth checking the up to √n, we upload a plus one because the
`vary()`

serve as excludes the endpoint of the variability by way of default.

The code cellular underneath verifies that our purposes `is_prime()`

works as it should be.

```
is_prime(8)
# False
is_prime(15)
# False
is_prime(23)
# True
```

In the following phase, allow us to create a few easy plots to perceive O(n) and O(√n) visually.

## Comparing O(n) and O(√n) Visually

▶️ Run the next code snippet in a Jupyter pocket book atmosphere of your selection.

```
import numpy as np
import seaborn as sns
import pandas as pd
n = 20
x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame("O(√n)":y1,"O(n)":y2)
sns.set_theme()
sns.lineplot(information = df)
```

The above snippet presentations how you’ll be able to plot the curves for n and √n for a vary of values.

- We use the NumPy arange() serve as to create an array of numbers.
- And then, we acquire the values of n and √n up to, however now not together with 20, into a pandas DataFrame.
- Next, we plot the use of seaborn’s lineplot() serve as.

From the plot underneath, we see that √n is considerably smaller than n.

Let us now build up the variability to as top as 2000 and repeat the similar 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("O(√n)":y1,"O(n)":y2)
sns.set_theme()
sns.lineplot(information = df)
```

From the above plot, you’ll be able to infer that O(√n) set of rules is considerably quicker whilst you’re checking out if a massive quantity is high.

Here’s a fast instance: 2377 is a high quantity—check this!😀

While the O(n) method will take the order of 2000 steps, the O(√n) set of rules can assist arrive on the resolution in simply 49 steps.✅

### Conclusion

⏳ And it’s time for a fast abstract.

- To take a look at if a quantity is high, the naïve method is to loop via all numbers in the variability (2, n-1). If you don’t in finding a issue that divides n, then n is high.
- As the one issue of n more than n/2 is n itself, you might make a selection to run handiest up to n/2.
- Both of the above approaches have a time complexity of O(n).
- As elements of a quantity happen in pairs, you’ll be able to run handiest up to √n. This set of rules is a lot quicker than O(n). And the acquire is considerable when checking if a massive quantity is high or now not.

I’m hoping you know the way to take a look at if a quantity is high in Python. As a subsequent step, you might take a look at our instructional on Python techniques on string operations—the place you’ll be told to take a look at if strings are palindromes, anagrams, and extra.

See you all in some other instructional. Until then, glad coding!👩🏽💻