# Check if number is Prime - Primality Test

Sun Feb 06 2022 04:24:25 GMT+0000 (UTC)

```// Time Complexity: O(N^1/2), Auxilliary Space: O(1)
//More Efficient Code(for large numbers)
//Almost 3x faster than Efficient Solution

import java.io.*;
import java.util.*;

public class Main {

static boolean isPrime(int n)
{
if(n==1)
return false;

if(n==2 || n==3)
return true;

if(n%2==0 || n%3==0)
return false;

for(int i=5; i*i<=n; i=i+6)
{
if(n % i == 0 || n % (i + 2) == 0)
return false;
}

return true;
}

//DRIVER CODE
public static void main (String[] args) {

//taking input using Scanner class
Scanner sc=new Scanner(System.in);

int T=sc.nextInt();//input testcases

while(T-->0)//while testcase have not been exhausted
{
Solution obj=new Solution ();
int N;
N=sc.nextInt();//input n
if(obj.isPrime(N))
System.out.println("Yes");
else
System.out.println("No");

}

}
}

//Efficient Code : Time Complexity : O(sqrt(n))

static boolean isPrime(int n)
{
if(n==1)
return false;

for(int i=2; i*i<=n; i++)
{
if(n % i == 0)
return false;
}

return true;
}

// Naive Method : Time Complexity : O(n)

static boolean isPrime(int n)
{
if(n == 1)
return false;
for(int i=2; i<n; i++)
{
if(n%i == 0)
return false;
}
return true;
}```
content_copyCOPY

7. Primality Test A prime number is a number which is only divisible by 1 and itself. Given number N check if it is prime or not. Example 1: Input: N = 5 Output: Yes Explanation: 5 is only divisible by 1 and itself. So, 5 is a prime number. Example 2: Input: N = 4 Output: No Explanation: 4 is divisible by 2. So, 4 is not a prime number. Your Task: You don't need to read input or print anything. Your task is to complete the function isPrime() that takes N as input parameter and returns True if N is prime else returns False. Expected Time Complexity: O(N^1/2) Expected Auxilliary Space: O(1) Constraints: 1 <= N <= 10^9

https://practice.geeksforgeeks.org/problems/primality-test/1/?track=DSASP-Mathematics&batchId=190