## Algorithm

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

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.

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 &

### #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 &

### #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 &

### #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 &

### #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 &

### #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 &

### #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 &

### #8 Code Example with PHP Programming

```Code - PHP Programming```

``````
;
}
}
?>
``````
Copy The Code &