# How to check if number is prime

Sat Jan 07 2023

Steps:

- check if number is less than 2, if so return false
- check if number is less than 3, if so return true
- check if number is divisible by 2, if so return false
- check if number is divisible by 3, if so return false
- check if number is divisible by any number between 5 and sqrt(number), if so return false
- why do we loop up to sqrt(number)?
- because if a number is not a prime number, it can be divided by a number that is smaller than its square root.
- for example, 12 can be divided by 2, 3, 4, 6, 12. 2 and 3 are smaller than 12's square root (3.46), so we can stop checking after 3.46.

- if we didn't find any number that divides the number, it is a prime number

```
def __is_prime(self, num: int) -> bool:
if num < 2:
return False
if num <= 3:
return True
if num % 2 == 0:
return False
if num % 3 == 0:
return False
for i in range(5, int(math.sqrt(num)) + 1, 2):
if num % i == 0:
return False
return True
```