Prime Number Program in Python

As a beginner or experienced programmer, you may encounter situations where you need to write code to determine whether a number is prime or not.

Prime numbers play a crucial role in number theory and have several applications in computer science, cryptography, and data science.

In this article, we will explore multiple ways to write a prime number program in Python and discuss various scenarios where you may need to use them.

What is a prime number?

Before we dive into writing the code, let's first understand what prime numbers are.

A prime number is a positive integer greater than 1 that has no positive integer divisors other than 1 and itself.

For example, 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29 are the first ten prime numbers.

Basic Algorithm to Check for Prime Numbers

The most straightforward algorithm to determine whether a number is prime or not is to check if it is divisible by any number less than itself.

We can use a for loop to iterate from 2 to n-1 and check if n is divisible by any of those numbers. If it is not divisible, it is a prime number.

def is_prime(n):
  # check if n is greater than 1
  if n <= 1:
    return False

  # check if n is divisible by any number less than n
  for i in range(2, n):
    if n % i == 0:
      return False

  # if n is not divisible by any number less than n, it is a prime number
  return True

print(is_prime(2)) # True
print(is_prime(3)) # True
print(is_prime(4)) # False

Optimized Algorithm to Check for Prime Numbers

The previous algorithm works for small numbers but becomes inefficient for larger numbers.

We can improve the efficiency by checking the divisibility of n only up to its square root. If n is not divisible by any number less than or equal to its square root, it is a prime number.

Here's the code for the same:

import math

def is_prime(n):
  # check if n is greater than 1
  if n <= 1:
    return False

  # check if n is divisible by any number less than or equal to its square root
  for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
      return False

  # if not False, it is a prime number
  return True

print(is_prime(20)) # False
print(is_prime(37)) # True

Prime Number Program in Python Using Sieve of Eratosthenes

The Sieve of Eratosthenes is an efficient algorithm to find all the prime numbers up to a given number n.

Here's how it works:

Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
Initially, let p equal 2, the smallest prime number.
Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, etc.; the p itself should not be marked).
Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

Here's the code for the same:

def sieve_of_eratosthenes(n):
  # create a list of consecutive integers from 2 through n
  numbers = list(range(2, n + 1))

  # initially, let p equal 2, the smallest prime number
  p = 2

  # loop through the numbers list
  while p <= n:
    # remove all multiples of p from the numbers list
    for i in range(p * 2, n + 1, p):
      if i in numbers:
        numbers.remove(i)

    # find the next number greater than p in the numbers list
    p += 1
    while p <= n and p not in numbers:
      p += 1

  return numbers

print(sieve_of_eratosthenes(20)) # [2, 3, 5, 7, 11, 13, 17, 19]

Prime Number Program in Python Using Sieve of Sundaram

The Sieve of Sundaram is another efficient algorithm to find all the prime numbers up to a given number n.

Here's how it works:

Create a list of consecutive integers from 1 through n: (1, 2, 3, ..., n).
Initially, let p equal 1, the smallest prime number.
Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, etc.; the p itself should not be marked).
Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

Here's the code for the same:

def sieve_of_sundaram(n):
  # create a list of consecutive integers from 1 through n
  numbers = list(range(1, n + 1))

  # initially, let p equal 1, the smallest prime number
  p = 1

  # loop through the numbers list
  while p <= n:
    # remove all multiples of p from the numbers list
    for i in range(p * 2, n + 1, p):
      if i in numbers:
        numbers.remove(i)

    # find the next number greater than p in the numbers list
    p += 1
    while p <= n and p not in numbers:
      p += 1

  # remove 1 from the numbers list
  numbers.remove(1)

  # double each number in the numbers list
  numbers = [2 * i + 1 for i in numbers]

  return numbers

print(sieve_of_sundaram(20)) # [2, 3, 5, 7, 11, 13, 17, 19]

Conclusion

So, that's how you can find all the prime numbers up to a given number in Python. We have covered three different algorithms to find all the prime numbers up to a given number in Python. You can use any of these algorithms depending on your requirements.

Hope you liked this article. Keep learning and keep coding!