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

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 h ere.

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.

Best 100+ Python Projects with source code

Also Read: