Algorithm

Problem Name: 30 days of code - Day 25: Running Time and Complexity

Problem Link: https://www.hackerrank.com/challenges/30-running-time-and-complexity/problem?isFullScreen=true

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.

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.

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

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


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

int main() {

    int T;
    long int n[T];
    scanf("%d",&T);
    for(int i = 0; i  <  T; i++){
        scanf("%ld",&n[i]);
        int flag=0;
        for(long int j=sqrt(n[i]);j > 1; j--){
            if(n[i]%j==0){
                flag=1;
                break;
            }
        }
        if(flag){
            printf("Not prime\n");
        }else
        if(n[i]==1){
            printf("Not prime\n");
        }else{
            printf("Prime\n");
        }
    }

    return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <cmath>
#include <iostream>

using namespace std;

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

int main() {
    int T;
    cin >> T;

    for (int i = 0; i  <  T; i++) {
        int n;
        cin >> n;

        if (n >= 2 && isPrime(n)) cout << "Prime" << endl;
        else cout << "Not prime" << endl;
    }
}
Copy The Code & Try With Live Editor

#3 Code Example with C# Programming

Code - C# Programming


using System;

class Solution
{
    public static bool isPrime(int n)
    {
        for (int i = 2; i  < = Math.Sqrt(n); i++)
        {
            if (n % i == 0)
            {
                return false;
            }
        }
        return true;
    }

    static void Main(String[] args)
    {
        var T = int.Parse(Console.ReadLine());

        for (int i = 0; i  <  T; i++)
        {
            int n = int.Parse(Console.ReadLine());

            if (n >= 2 && isPrime(n)) Console.WriteLine("Prime");
            else Console.WriteLine("Not prime");
        }
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Golang Programming

Code - Golang Programming


package main

import (
	"fmt"
	"math"
)

func checkPrime(num float64) string {
	var i int
	if num == 1 || (num != 2 && int(num)%2 == 0) {
		return "Not prime"
	}

	for i = 3; i  < = int(math.Sqrt(num)); i += 2 {
		if int(num)%i == 0 {
			return "Not prime"
		}
	}
	return "Prime"
}

func main() {
	var t int
	fmt.Scan(&t)

	s := make([]float64, t)

	for k := range s {
		fmt.Scan(&s[k])
	}

	for _, v := range s {
		fmt.Println(checkPrime(v))
	}
}
Copy The Code & Try With Live Editor

#5 Code Example with Java Programming

Code - Java Programming


import java.util.Scanner;

public class Solution {
    public static boolean isPrime(int n) {
        for (int i = 2; i  < = Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();

        for (int i = 0; i  <  T; i++) {
            int n = in.nextInt();

            if (n >= 2 && isPrime(n))
                System.out.println("Prime");
            else System.out.println("Not prime");
        }

        in.close();
    }
}
Copy The Code & Try With Live Editor

#6 Code Example with Javascript Programming

Code - Javascript Programming


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);
  }>;
Copy The Code & Try With Live Editor

#7 Code Example with Python Programming

Code - Python Programming


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")
Copy The Code & Try With Live Editor

#8 Code Example with PHP Programming

Code - PHP Programming


;
    }
}
?>
Copy The Code & Try With Live Editor
Advertisements

Demonstration

Previous
[Solved] Day 24: More Linked Lists solution in Hackerrank - Hacerrank solution C, C++, C#, java, Js, Python & PHP in 30 days of code
Next
[Solved] Day 26: Nested Logic solution in Hackerrank - Hacerrank solution C, C++, C#, GO, java, Js, Python & PHP in 30 days of code