Day 25 Running Time and Complexity Hacker Rank Solution In C++

Problem:- Day 25 Running Time and Complexity hackerrank or HR-30-days-of-code/day25-Running Time and Complexity or running time and complexity hackerrank solution in c++ or running time and complexity solution or day 25 hackerrank solution or day 25 solution in c++ or hackerrank day 25 solution in c or hackerrank Day 25 Running Time and Complexity solution or hackerrank Running Time and Complexity solution

Task:- 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's Prime or Not Prime.

Note: If possible, try to come up with a 0(square root(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.

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

Submit this solution:- Click Here

Solution:-

#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;

}

Output:-