# Day 25: Running Time and Complexity | 30 Days Of Code | HackerRank Solution

Hello coders, today we are going to solve Day 25: Running Time and Complexity HackerRank Solution in C++, Java and Python.

## Objective

Today we will learn about running time, also known as time complexity.

prime is a natural number greater than 1 that has no positive divisors other than 1 and itself. Given a number, n, determine and print whether it is Prime or Not prime.

Note: If possible, try to come up with a O(n1/2) primality algorithm, or see what sort of optimizations you come up with for an  algorithm. Be sure to check out the Editorial after submitting your code.

## Input Format

The first line contains an integer, T, the number of test cases.
Each of the T subsequent lines contains an integer, n, to be tested for primality.

## Constraints

• 1 <= T <= 30
• 1 <= n <= 2 x 109

## Output Format

For each test case, print whether n is Prime or Not Prime on a new line.

Sample Input

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

Sample Output

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

Explanation

Test Case 0: n = 12.
12 is divisible by numbers other than 1 and itself (i.e.: 2346), so we print Not Prime on a new line.

Test Case 1: n = 5.
5 is only divisible 1 and itself, so we print Prime on a new line.

Test Case 2: n = 7.
7 is only divisible 1 and itself, so we print Prime on a new line.

## Solution – Day 25: Running Time and Complexity

### C++

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T;
cin >> T;
for (size_t t = 0 ; t < T ; ++t) {
int n;
bool prime = true;
cin >> n;
if (n > 1) {
for (size_t i = pow(M_E, log(n)/2) ; i > 1 ; --i) {
if ( !(n % i) ) {
prime = false;
break;
}
}
} else {
prime = false;
}
if ( prime ) {
cout << "Prime" << endl;
} else {
cout << "Not prime" << endl;
}
}
return 0;
}```

### Java

```import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

static void prime(int n)
{
boolean flag=false;
for(int i=2;i<=Math.sqrt(n);i++)
{
if(n%i==0)
{
flag=true;
break;
}
}
if(n==1){
System.out.println("Not prime");
}
else if(!flag){
System.out.println("Prime");
}

else{
System.out.println("Not prime");
}
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t--!=0)
{
int n=sc.nextInt();
prime(n);
}
}
}
```

### Python

```from math import sqrt
from sys import stdin

def checkPrime(n):
for i in range(2, int(sqrt(n))+1):
if n % i is 0:
return False
return True

n = int(input())
for line in stdin:
val = int(line)
if (val >= 2 and checkPrime(val)):
print("Prime")
else:
print("Not prime")```

Disclaimer: The above Problem (Day 25: Running Time and Complexity) is generated by Hacker Rank but the Solution is Provided by learnkro.com. This tutorial is only for Educational and Learning Purpose.