Prime Number Program in Python: Four Simple Ways to Check a Number

Learning how to write a prime number program in Python is a helpful exercise for anyone beginning programming. The problem looks simple, but it teaches several important ideas, including conditional statements, loops, functions, recursion, and algorithm efficiency.

In this article, we will learn how to check whether a positive integer is prime. We will begin with a straightforward method using a flag variable and then explore three additional approaches: Python’s isprime() function from SymPy, the Sieve of Eratosthenes, and recursion.

What Is a Prime Number?

A prime number is a whole number greater than 1 that has exactly two factors: 1 and the number itself.

For example, 29 is a prime number because it can be divided evenly only by 1 and 29. The number 10 is not prime because it has several factors, including 1, 2, 5, and 10.

Some examples are:Copy

Prime numbers: 2, 3, 5, 7, 11, 13, 17, 19
Not prime: 1, 4, 6, 8, 9, 10

It is important to remember that 1 is not a prime number. A prime number must have two factors, while 1 has only one factor.

Method 1: Check for a Prime Number Using a Flag Variable

The first method uses a Boolean variable called prime to remember whether the number is still considered prime.Copy

n = 29

if n <= 1:
    print("Not a Prime Number")
else:
    prime = True

    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            prime = False
            break

    if prime:
        print("Prime Number")
    else:
        print("Not a Prime Number")

Output

Copy

Prime Number

How This Program Works

The first condition checks whether the number is less than or equal to 1:Copy

if n <= 1:

Numbers in this group cannot be prime, so the program immediately prints that the number is not prime.

Next, the program creates a variable named prime and gives it the value True:Copy

prime = True

At this point, the program assumes that the number is prime. It will change the value to False if it finds a divisor.

The loop checks possible divisors from 2 to the square root of n:Copy

for i in range(2, int(n ** 0.5) + 1):

The expression n ** 0.5 calculates the square root of n. Checking only up to the square root makes the program faster than checking every number up to n - 1.

Inside the loop, the remainder operator checks whether n divides evenly by i:Copy

if n % i == 0:

If the remainder is zero, a divisor has been found. Therefore, the number is not prime:Copy

prime = False
break

The break statement stops the loop because there is no need to perform more checks.

Example With a Non-Prime Number

If you change the value to 10:Copy

n = 10

The program finds that 10 is divisible by 2 and prints:Copy

Not a Prime Number

This is usually the best method for beginners because it clearly shows the logic used to solve the problem.

Method 2: Use the isprime() Function From SymPy

If you are working on a larger mathematical or scientific Python project, you can use the isprime() function from the SymPy library.

First, install SymPy if it is not already installed:Copy

pip install sympy

Then use the following code:Copy

from sympy import isprime

n = 13
print(isprime(n))

Output

Copy

True

The isprime() function returns True when the number is prime and False when it is not.

For example:Copy

from sympy import isprime

print(isprime(29))
print(isprime(10))

Output

Copy

True
False

This approach is very short and convenient. However, it is useful to understand the basic algorithm before depending on a library function. When you write the logic yourself, you learn exactly how a prime number check works.

Method 3: Use the Sieve of Eratosthenes

The Sieve of Eratosthenes is useful when you need to find prime numbers up to a maximum value, rather than checking only one number.

For example, the following function determines whether a number is prime while creating a list of prime statuses up to that number:Copy

def is_prime(n):
    if n < 2:
        return False

    status = [True] * (n + 1)
    status[0] = status[1] = False

    for i in range(2, int(n ** 0.5) + 1):
        if status[i]:
            for j in range(i * i, n + 1, i):
                status[j] = False

    return status[n]

print(is_prime(31))

Output

Copy

True

How the Sieve Works

The list named status stores whether each number is potentially prime. Initially, every position is set to True:Copy

status = [True] * (n + 1)

The values at positions 0 and 1 are changed to False because neither number is prime:Copy

status[0] = status[1] = False

The outer loop visits possible prime numbers. When it finds one, the inner loop marks all of its multiples as non-prime.

For example, if i is 2, the program marks 4, 6, 8, 10, and other multiples of 2 as False.

The inner loop begins at i * i because smaller multiples have already been handled by earlier numbers:Copy

for j in range(i * i, n + 1, i):

At the end, status[n] tells us whether the target number is prime.

The Sieve of Eratosthenes is especially useful for generating a complete list of prime numbers within a range.

Method 4: Check for a Prime Number Using Recursion

Recursion happens when a function calls itself. In this example, the function checks one possible divisor and then calls itself with a smaller divisor.Copy

from math import sqrt

def prime(n, i):
    if i == 1:
        return True

    if n % i == 0:
        return False

    return prime(n, i - 1)

n = 13
print(prime(n, int(sqrt(n))))

Output

Copy

True

The function receives two values: the number being checked, n, and the current divisor, i.

The first condition is the stopping condition:Copy

if i == 1:
    return True

If the function reaches 1 without finding a divisor, the number is considered prime.

The next condition checks whether n is evenly divisible by i:Copy

if n % i == 0:
    return False

If a divisor is found, the function returns False.

If there is no divisor, the function calls itself with i - 1:Copy

return prime(n, i - 1)

Although recursion is an interesting way to solve the problem, a loop is usually easier for beginners to read. Recursion can also use more memory when many function calls are made.

Which Method Should You Use?

Each method has a different purpose:

For your first prime number program in Python, start with the flag-variable approach. Once you understand it, try rewriting the program as a function and then experiment with the other methods.

Common Mistakes to Avoid

Treating 1 as a prime number

The number 1 is not prime because it does not have two factors. Always handle values less than 2 separately.

Checking divisibility by 1

Every whole number is divisible by 1, so checking it does not help. Start the divisor loop at 2.

Forgetting the square-root limit

Checking up to the square root is enough and improves performance. Remember to add 1 to the range limit because Python excludes the ending value.

Forgetting to stop after finding a divisor

Once a divisor is found, use break in a loop or return False from a function. Continuing to check is unnecessary.

Conclusion

A prime number program in Python is a small project with many valuable lessons. It shows how to use the modulo operator, conditions, loops, functions, lists, external libraries, and recursion.

The flag-variable method is the clearest starting point for beginners. The isprime() method is convenient, the Sieve of Eratosthenes is useful for checking many numbers, and recursion provides an alternative way to express the logic.

Try changing the examples and testing numbers such as 2, 7, 10, 29, 31, and 100. You can also extend the program to print every prime number between two inputs, count the primes in a range, or build a simple prime-number quiz. Practising these variations will help you become more comfortable with Python fundamentals.