Home30 Days Of CodeHackerRank Day 25: Running Time and Complexity 30 days of code solution

# HackerRank Day 25: Running Time and Complexity 30 days of code solution

Today we are going to solve HackerRank Day 25: Running Time and Complexity 30 days of code solution 30 days of code solution in C++, Java & 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.

## Running Time and Complexity HackerRank Solution in C

``````#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int isPrime(int n) {
int i;
int res = 1;
if (n < 2) {
return 0;
}

for (i = 2; i < sqrt(n); i++) {
if (n % i == 0) {
res = 0;
break;
}
}

return res;
}
int main() {

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int i;
int t;
int n;
scanf("%d", &t);
for (i = 0; i < t; i++) {
scanf("%d", &n);
if (isPrime(n)) {
printf("Prime\n");
} else {
printf("Not prime\n");
}
}

return 0;
}``````

## Running Time and Complexity HackerRank Solution in 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(int t = 0; t < T; t++){
int n;
cin >> n;
if(n == 1){
printf("Not prime\n");
continue;
}
if(n <= 3){
printf("Prime\n");
continue;
}
if(n % 2 == 0 || n % 3 == 0){
printf("Not prime\n");
continue;
}

bool prime = true;
int sqRoot = sqrt(n);
for(int i = 3; i <= sqRoot; i+=2){
if(n % i == 0){
prime = false;
break;
}
}
if(prime){
printf("Prime\n");
} else {
printf("Not prime\n");
}

}
return 0;
}``````

## Running Time and Complexity HackerRank Solution in Java

``````import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner sc = new Scanner(System.in);
final int N = sc.nextInt();
for (int i = 0; i < N; i++) {
if (isPrime(sc.nextInt()))
System.out.println("Prime");
else
System.out.println("Not prime");
}
}

private static boolean isPrime(int num) {
if (num == 1) return false;
for (int i = 2; i < Math.sqrt(num); i++)
if (num % i == 0) return false;
return true;
}
}``````

## Running Time and Complexity HackerRank Solution in Python 3

``````from math import sqrt

T = int(input())

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

for _ in range(T):
n = int(input())

if n >= 2 and isPrime(n):
print("Prime")
else:
print("Not prime")``````

## Running Time and Complexity HackerRank Solution in Python 2

``````# Enter your code here. Read input from STDIN. Print output to STDOUT
import math

N = int(raw_input().strip())

def isPrime(n):
if n < 2:
return False
elif n < 4:
return True
else:
prime = True
for i in xrange(2, int(math.sqrt(n))):
if (n % i == 0):
prime = False
break
return prime

for i in xrange(N):
num = int(raw_input().strip())
if isPrime(num):
print "Prime"
else:
print "Not prime"``````

## Running Time and Complexity HackerRank Solution in Javascript

``````function processData(input) {
var arr = input.split('\n');
for (var i = 1; i < arr.length; i++){
var n = arr[i];
if(isPrime(n)){
console.log("Prime");
} else {
console.log("Not prime");
}
}
}

function isPrime(n){
if (n <= 1)  {
return false;
}
if (n <= 3) {
return true;
}

// This is checked so that we can skip
// middle five numbers in below loop
if (n%2 == 0 || n%3 == 0){
return false;
}

for (var index=5; index*index<=n; index=index+6){
if (n%index == 0 || n%(index+2) == 0) {
return false;
}
}
return true;
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});

process.stdin.on("end", function () {
processData(_input);
});``````

30 Days of Code HackerRank Solutions List – Day 0 to Day 29

RELATED ARTICLES