HackerRank Time Complexity: Primality problem solution

In this HackerRank Time Complexity: Primality Interview preparation kit problem You have Given p integers, determine the primality of each integer and return Prime or Not prime on a new line.

Problem solution in Python programming.

from math import *
p = int(input().strip())
for a0 in range(p):
    n = int(input().strip())
    f=5
    if(n!=1):
        for i in range(2,int(sqrt(n))):
            if(n%i==0):
                f=0
    if(f==0 or n==1):
        print("Not prime")
    else:
        print("Prime")

Problem solution in Java Programming.

import java.io.*;
public class Solution {
    static int prime(int x)
    {
        int k=1;
        if(x==1)
            k=0;
        else if(x==2)
            k=1;
        else if(x%2==0)
            k=0;
        else
        {
            for(int i=3;i*i<=x;i+=2)
           {
              if(x%i==0)
              {
                  k=0;
                  break;
              }
           }
        }
        return k;
    }
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try
       {
             int p = Integer.parseInt(br.readLine());
            int i,j,k,l;
             for(i=0;i<p;i++)
             {
                 j = Integer.parseInt(br.readLine()); 
                 k = prime(j);
                 if(k==1)
                     System.out.println("Prime");
                 else
                     System.out.println("Not prime");
             }
        }
        catch(IOException e)
            {
            System.out.println(e);
        }
    }
}

Problem solution in C++ programming.

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;


int main(){
    int p;
    cin >> p;
    for(int a0 = 0; a0 < p; a0++){
        int n;
        cin >> n;
        bool isprime = true;
        for (auto j = 2; j <= sqrt(n); ++j) {
            if ( n%j == 0) {
                isprime = false;
                break;
            }
        }
        if ( n == 0 || n == 1) isprime = false;
        if ( isprime) cout << "Prime" << endl;
        else cout << "Not prime" << endl    ;
    }
    
    
    return 0;
}

Problem solution in C programming.

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

bool fermat_test(int N, int iterations);
int modulo(int a, int b, int c);

int main(int argc, char const *argv[])
{
	int p, n;
    scanf("%d", &p);
	int i;
	for(i = 0; i < p; i++){
       scanf("%d", &n);	
	   if(fermat_test(n, 50)) printf("Primen");
	   else printf("Not primen");
    }
    
	return 0;
}


bool fermat_test(int N, int iterations){
	int i;
	if(N == 1){
		return false;
	}
	for(i = 0; i < iterations; i++){
		int a = rand()%(N-1)+1;
		if(modulo(a, N-1, N) != 1){
			return false;
		}
	}
	return true;
}

int modulo(int a,int b,int c){
    long long x=1,y=a; // long long is taken to avoid overflow of intermediate results
    while(b > 0){
        if(b%2 == 1){
            x=(x*y)%c;
        }
        y = (y*y)%c; // squaring the base
        b /= 2;
    }
    return x%c;
}

Problem solution in JavaScript programming.

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function main() {
    var p = parseInt(readLine());
    for(var a0 = 0; a0 < p; a0++){
        var n = parseInt(readLine());
        console.log(isPrime(n) ? 'Prime' : 'Not prime');
    }

    function isPrime(n) {
        for (let i = 2; i <= Math.sqrt(n); i++) {
            if (n % i === 0) {
                return false;
            }
        }
        return n !== 1;
    }
}