**What is a Prime Number?**

A **Prime Number** is a number which is greater than **1** and divisible by** 1** and only **itself**. Some of the **Prime Numbers** are **2, 3, 5, 7, 11, 13, 17… **In this article, let’s create a **Prime Number Program in Python** and learn some **Optimization techniques**.

## Prime Number Program in Python

**Is 0 a prime number?**

**0** is neither **prime** nor **composite** number, as per the definition, a prime number is a number with **exactly two positive divisors**, **1 **and **itself**. **Zero** has an **infinite number of divisors** (we can divide **0** by all real numbers) Therefore, **zero** is **not** a **Prime Number**.

**Is 1 a prime number?**

**1** is not considered as a **Prime **because it does not meet the criteria which is exactly two factors **1** and **itself**, whereas **1** has only **one** factor

**Create a CheckPrime function**

We all know that the prime numbers can only be divided by **itself** and **1**.

If the **number** is **less than** **1,** then it cannot be considered as prime. The idea behind the below code is to scan through all the integers between **2** and **number-1**, and if anyone of them is the **divisor** of the **number,** then the given number is **not prime**.

We use the **modulo division** to check if the number is getting divided or not. Modulo division gives us the remainder of the division. If the **remainder** is **zero,** then the number is **not prime.**

def checkPrime(number): if number < 1: return False for i in range (2, number): if number % i == 0: return False return True number = input("Enter a number to check prime ") prime = checkPrime(int(number)) if prime: print(f"{number} is a prime number") else: print(f"{number} is not a prime number")

**Using While loop**

Let’s re-write the above code using the **while loop**.

def checkPrime(number): if number < 1: return False i = 2 while i < number: if number % i == 0: return False i += 1 return True number = input("Enter a number to check prime ") prime = checkPrime(int(number)) if prime: print(f"{number} is a prime number") else: print(f"{number} is not a prime number")

The drawback of this approach is that we need to increment the **i variable** used in the while loop manually.

**Optimization Techniques:**

**Technique 1: Using Square Root**

While checking for **Prime**, we don’t have to check if the number is divisible by all the numbers till **number -1**. We can further optimize the above code by adding a simple range change, to check for the divisors up to the **square root** of the **number**.

Because for any number, there can be at least **two factors**, and one of those factors must be **smaller** **than or equal** to the **square** **root** of the **number**. If this is not **true** and both factors were larger than the **square root **of the** number** then the resulting number would be larger the **number** itself.

Let’s take an example **36 **and analyze the factors of it, and they are **1, 2, 3, 4, 6, 9, 12, 18.**

**1 x 36 = 36**

**2 x 18 = 36**

**3 x 12 = 36**

**4 x 9 = 36**

**6 x 6 = 36**

So, we can just iterate till **6** to find out the factors of **36**

import math def checkPrime(number): if number < 1: return False for i in range (2, int(math.sqrt(number))+1): if number % i == 0: return False return True number = input("Enter a number to check prime ") prime = checkPrime(int(number)) if prime: print(f"{number} is a prime number") else: print(f"{number} is not a prime number")

**Time Complexity** of the above algorithm to find factors is *O(sqrt(N))*

**Technique 2: Sieve of Eratosthenes**

**Sieve of Eratosthenes** works on the principle of identifying the **smallest prime **and eliminating all the **multiples** of that prime within the **range.**

Let’s use the **Sieve of Eratosthenes** approach to find prime numbers between **1 **to **25**. We need to iterate till the square root of **25, **which is **5.**

**[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]**

Since 1 is not a prime, we can remove it.

**[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]**

The smallest prime is **2, **and start the iteration from **2 **to **sqrt(number), **let’s keep** 2** and strikeout all the numbers which are divisible by **2**

**[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]**

Now the next prime is **3,** keep** 3** and strikeout all the multiples of **3**

**[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]**

Since **4** is stricken out, repeat the process with **5**

**[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]**

Now, all the numbers we have are prime.

**[2, 3, 5, 7, 11, 13, 17, 19, 23]**

let’s implement **Sieve of** **Eratosthenes in Python**

def checkPrime(number): numbersList = list(range(2,number+1)) for i in range(2,int(number**0.5)+1): for j in range (i*i, number+1, i): if j in numbersList: numbersList.remove(j) return numbersList number = int(input("Enter the range to check for prime ")) prime = checkPrime(number) print(f"******* Prime numbers between 1 to {number} **********") print(*prime)

**Technique 3: Optimized School Method [6n + 1 or 6n – 1]**

The **Lowest** **even prime is 2** and the **lowest odd prime is 3**. Apart from these two numbers all the prime numbers greater than **3** can be expressed in the form of **6n + 1 **or **6n -1.**

def checkPrime(number): if number <= 1: return False if number == 2 or number == 3: return True if number % 2 == 0 or number % 3 == 0: return False i = 5 while(i * i <= number): if (number % i == 0 or number % (i + 2) == 0): return False i = i + 6 return True number = int(input("Enter a number to check for prime ")) prime = checkPrime(number) if prime: print(f"{number} is a prime number") else: print(f"{number} is not a prime number")

In the above code, we are checking the following conditions

- When the number is
**less than**or**equal**to**1**then return**false**as it is not a prime - Add exclusion for
**2**and**3**, if the number is**2**or**3**then return**true** - If the number is a multiple of
**2**or**3**then return**false** - The loop starts with
**5**, which is**6n – 1**and test**n % ( i + 2 )**which is**6n + 1**

**Python Prime Number Generator**

To implement the Python prime number generator, we need to get the **start** and **end** range from the user and implement **Sieve of Eratosthenes** to generate all the possible prime numbers with the range.

def checkPrime(start, end): numbersList = list(range(start, end+1)) for i in range(2,int(end**0.5)+1): for j in range (i*i, end+1, i): if j in numbersList: numbersList.remove(j) return numbersList start = int(input("Enter the Starting range ")) end = int(input("Enter the Ending range ")) primeNumberList = checkPrime(start, end) print(f"******* Prime numbers between {start} to {end} **********") print(*primeNumberList)

**Output:**

Enter the Starting range 2 Enter the Ending range 100 ******* Prime numbers between 2 to 100 ********** 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Happy Learning!!

## Leave a Reply