# 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!