# HackerRank Day 25 Solution in Python: Running Time and Complexity

Today we will see the HackerRank Day 25 Solution in Python. The problem is named Running Time and Complexity which is part of 30 Days of code on HackerRank. Let’s get started!

## Day 25: Running Time and Complexity Problem statement

We have to come up with an O(√n) primality algorithm or see what sort of optimizations we come up with for an O(n) algorithm. A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself. We are given a number, n, our task is to determine and print whether it is Prime or Not Prime.

Sample Input

``````3
12
5
7``````

Sample Output

``````Not prime
Prime
Prime``````

Explanation

The first input is the number of integers to predict. 12 is not a prime, 5 and 7 are prime numbers

You can solve the problem here.

## HackerRank Day 25 Solution in Python

```import math

#Input for number of testcase
t = int(input())

for i in range(t):
inp = int(input())

if is_prime(inp):
print("Prime")
else:
print("Not prime")

#Function to find prime or not
def is_prime(num):
if num == 1 or num == 0:
return False

for i in range(2, int(math.sqrt(num)) + 1):
if (num % i) == 0:
return False

return True```

## Code Explanation

• First, we get the number of input from the user
• Then we create a function to find whether the number is prime or not
• If the number is 0 or 1 then return false
• Else create a loop from 2 to sqrt(n) to check whether any number is divisible by the input. If it is divisible then return false
• Else return true
• If the returned value is true then print Prime, Otherwise print Not Prime. 