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.

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 is Prime or Not prime.

Note: If possible, try to come up with a O(n^1/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 10⁹

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

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 CodingBroz. This tutorial is only for Educational and Learning Purpose.