# Day 25 Running Time And Complexity Hackerrank Solution in C++

Day 25 Running Time And Complexity Hackerrank Solution In C++. This problem is a subset of Hackerrank's 30 Days of Code. If a number (n) isn't divisible by all the numbers in the inclusive range from 2 to the integer square root of that number (n ** 0.5) then that number is prime.

Objective

Today we will learn about running time, also known as time complexity. Check out the Tutorial tab for learning materials and an instructional video.

A 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 an O(√n) primality algorithm, or see what sort of optimizations you come up with for an O(n) 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 * 10^9

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.: 2, 3, 6 ), so we print Not Prime on a new line.
Test Case 1: n = 5.
5 is only divisible by 1 and itself, so we print Prime on a new line.
Test Case 2: n = 7.
7 is only divisible by 1 and itself, so we print Prime on a new line.

## Running Time And Complexity Hackerrank Solution in C++

#include <bits/stdc++.h>

using namespace std;

bool primeornot(int);

int main() {
int n, i;
bool f;
cin >> n;

vector < int > arr(n);
for (i = 0; i < n; ++i) {
cin >> arr[i];
bool f = primeornot(arr[i]);

if (f) {
cout << "Prime" << endl;
} else {
cout << "Not prime" << endl;
}
}
return 0;
}

bool primeornot(int n) {
int i, sqr;
if (n == 1) {
return false;
}
if (n == 2) {
return true;
}
sqr = sqrt(n);
for (i = 2; i <= sqr; ++i) {
if (n % i == 0) {
return false;
}
}
return true;

}

### Similar to 30 Days of Code

Previous Post
Next Post

#### post written by: Ghanendra Yadav

Hi, I’m Ghanendra Yadav, SEO Expert, Professional Blogger, Programmer, and UI Developer. Get a Solution of More Than 500+ Programming Problems, and Practice All Programs in C, C++, and Java Languages. Get a Competitive Website Solution also Ie. Hackerrank Solutions and Geeksforgeeks Solutions. If You Are Interested to Learn a C Programming Language and You Don't Have Experience in Any Programming, You Should Start with a C Programming Language, Read: List of Format Specifiers in C.