# Program to check if the given number is Prime or not in Python

## Prime or not in Python

In this article we will see a program to find whether a number is Prime or not in Python. A number is said to be a prime number if and only if it is only divisible by 1 or itself (factors==>1,number itself) . If a number has more than two factors than the number is said to be not a prime number.
• Sample input: 17
• Sample output: The given number is prime
See the two different approaches below , solution 1 is more efficient than solution 2

## Method 1

### Algorithm:

• Step 1: Initialize the variable a and count to zero
• Step 2: Read the input
• Step 3: Set a to n//2 (// in python implies integer division) , we can make a to square root of number to make it more efficient
• Step 4: iterate through 2 to a+1 and check whether it is divisible by i or not
• Step 5 : if divisible , then print “not a prime number” and set count to 1 and break from the loop
else continue iteration
• Step 6 : if count is still zero then the given number is prime number

### Python code:

```a = 0
count = 0
n=int(input("Enter the number to check if it is prime or not: "))
a = n // 2;

for i in range(2,a+1):
if (n % i == 0):
print("The given number is not prime")
count = 1
break
if (count == 0):
print("The given number is prime")```
`Enter the number to check if it is prime or not: 17The given number is prime`

## Method 2

### Algorithm

• Step 1: Take an empty array
• Step 2: Read the number
• Step 3: Iterate a  from 1 to the number
• Step 4: If number is divisible by iterator i then append the number to factors array
• Step 5: if length of factors array is 2 then given number is prime
else the given number is not prime number
(for more clarity factors of numbers also printed)

### Python Code:

```factors=[ ]
n=int(input(“Enter the number to check if it is prime or not: “))
for i in range(1,n+1):
if (n % i == 0):
factors.append(i)
if (len(factors)==2):
print(“The given number is prime”)
else:
print(“The given number is not prime number”)
print(“Factors of given number is”,factors)```
`Enter the number to check if it is prime or not: 16The given number is not prime number[1, 2, 4, 8, 16]`