Time Complexity: Primality

                            Solution in C :

In    C   :






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

int main(){
    int p; 
    int flag;
    scanf("%d",&p);
    for(int a0 = 0; a0 < p; a0++)
    {
        flag=0;
        int n; 
        scanf("%d",&n);
        if(n==1)
            {
                        printf("Not prime\n");
                        flag=1;
                        break;                
            }
        if(flag!=1){
        for(int i=2;i<=sqrt(n);i++)
        {
            
            if(n%i==0 || (n%(n/i))==0)
                {
                    printf("Not prime\n");
                    flag=1;
                    break;
                }
            
        }
        }
        if(flag==0)
        {
            printf("Prime\n");
        }
    }   
    return 0;
    }
                        

                        Solution in C++ :

In   C++  :






#include <iostream>
#include <math.h>
using namespace std;

int main(){
	int soLanNhapVao, soNhapVao;
	int soUoc = 1;
	cin >> soLanNhapVao;
	for(int i = 0;i < soLanNhapVao;i++){
		cin >> soNhapVao;
		for(int j = 2;j < sqrt(soNhapVao);j++){
			if(soNhapVao%j == 0){
				soUoc += 1;
			}
			else{
			}
		}
        if(soNhapVao == 1){
            cout << "Not prime" << endl;
        }
		else if(soUoc >= 2){
			cout << "Not prime" << endl;
			soUoc = 1;
		}
		else{
			cout << "Prime" << endl;
			soUoc = 1;
		}
	}
}
                    

                        Solution in Java :

In  Java  :







import java.util.*;

public class Solution {

    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 sc = new Scanner(System.in);
        int numOfTests = sc.nextInt();
        for (int i = 0; i < numOfTests; i++) {
            int x = sc.nextInt();
            String s;
            if (x >= 2 && isPrime(x)) {
                s = "Prime";
            } else {
                s = "Not prime";
            } 
            System.out.println(s);
        }
    }
}
                    

                        Solution in Python : 
                            
In   Python3  :







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")