# 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) {
try
{
int i,j,k,l;
for(i=0;i<p;i++)
{
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("Prime\n");
else printf("Not prime\n");
}

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();
});

return input_stdin_array[input_currentline++];
}

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

function main() {
for(var a0 = 0; a0 < p; a0++){
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;
}
}```