How To Find Prime Numbers In Python

Prime numbers are numbers that are divisible only by 1 and themselves. For example, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 are prime numbers.

Prime numbers have many applications in computer science and mathematics, and Python provides us with an efficient way to find prime numbers. In this tutorial, we will explore the various ways we can find prime numbers in Python.

Steps

Step 1: Using a for-loop to check if a number is prime

The easiest way to determine if a number is prime is to check if it is divisible by any number less than itself. We can use a for-loop to achieve this in Python.

We will start our loop at 2 (since 1 is not considered a prime number), and continue until we reach the number we want to check.

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

To use this function, we simply call it and pass in the number we want to check. The function will return True if the number is prime, and False otherwise.

1
2
print(is_prime(5))
print(is_prime(6))

Step 2: Using the math library

Python also provides us with math.sqrt () function, which returns the integer square root of a number. We can use this function to improve the efficiency of our prime checking function by reducing the range of the for-loop.

1
2
3
4
5
6
7
8
9
10
11
import math
 
def is_prime_improved(n):
    if n == 2:
        return True
    if n % 2 == 0 or n == 1:
        return False
    for i in range(3, math.isqrt(n) + 1, 2):
        if n % i == 0:
            return False
    return True

In this function, we first check if the number is 2 (the only even prime number), or if it is even or 1 (which are not prime).

We then use the math.isqrt() function to find the square root of the number and round up to the nearest integer. We then start our loop at 3 and increment by 2 (to skip even numbers) until we reach the square root of the number.

The rest of the function is the same as before – if we find a number that divides without remainder, we return False. Otherwise, we return True.

Conclusion

In this tutorial, we learned how to find prime numbers in Python using a for-loop and the math library. By using these methods, we were able to efficiently determine whether a number is prime or not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import math
 
def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True
 
def is_prime_improved(n):
    if n == 2:
        return True
    if n % 2 == 0 or n == 1:
        return False
    for i in range(3, math.isqrt(n) + 1, 2):
        if n % i == 0:
            return False
    return True
 
print(is_prime(5))
print(is_prime(6))

Output:

True
False