Snippets Collections
// 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;
	}
star

Sun Feb 06 2022 04:24:25 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/primality-test/1/?track=DSASP-Mathematics&batchId=190

#java #mathematics #lecture #gfg #geeksforgeeks #efficientmethod #naivemethod #isprime #primalitytest

Save snippets that work with our extensions

Available in the Chrome Web Store Get Firefox Add-on Get VS Code extension