```// Efficient Method : Time Complexity : θ(logn), Auxiliary Space: θ(1)

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

public class Main {

static int power(int x, int n)
{
int res = 1;

while(n>0)
{
if(n%2 != 0)
{
res = res * x;
x = x*x;
n = n/2;
}
else
{
x = x*x;
n = n/2;
}
}

return res;
}

public static void main (String[] args) {

int x = 3, n = 4;

System.out.println(power(x, n));

}
}```
```// Efficient Method : Time Complexity : θ(logn), Auxiliary Space: θ(logn)

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

public class Main {

static int power(int x, int n)
{
if(n == 0)
return 1;

int temp = power(x, n/2);

temp = temp * temp;

if(n % 2 == 0)
return temp;
else
return temp * x;
}

public static void main (String[] args) {

int x = 3, n = 5;

System.out.println(power(x, n));

}
}

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

static int power(int x, int n)
{
int res = 1;

for(int i=0; i<n; i++)
{
res = res * x;
}

return res;
}```
```// Shorter Implementation of the optimized sieve :

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

public class Main {

static void sieve(int n)
{
if(n <= 1)
return;

boolean isPrime[] = new boolean[n+1];

Arrays.fill(isPrime, true);

for(int i=2; i <= n; i++)
{
if(isPrime[i])
{
System.out.print(i+" ");
for(int j = i*i; j <= n; j = j+i)
{
isPrime[j] = false;
}
}
}
}

public static void main (String[] args) {

int n = 23;

sieve(n);

}
}

//Optimized Implementation : Time Complexity : O(nloglogn), Auxiliary Space : O(n)

static void sieve(int n)
{
if(n <= 1)
return;

boolean isPrime[] = new boolean[n+1];

Arrays.fill(isPrime, true);

for(int i=2; i*i <= n; i++)
{
if(isPrime[i])
{
for(int j = i*i; j <= n; j = j+i) // Replaced 2*i by i*i
{
isPrime[j] = false;
}
}
}

for(int i = 2; i<=n; i++)
{
if(isPrime[i])
System.out.print(i+" ");
}
}

//Simple Implementation of Sieve :

static void sieve(int n)
{
if(n <= 1)
return;

boolean isPrime[] = new boolean[n+1];

Arrays.fill(isPrime, true);

for(int i=2; i*i <= n; i++)
{
if(isPrime[i])
{
for(int j = 2*i; j <= n; j = j+i)
{
isPrime[j] = false;
}
}
}

for(int i = 2; i<=n; i++)
{
if(isPrime[i])
System.out.print(i+" ");
}
}

//Naive Solution : Time Complexity : O(n(sqrt(n))

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

static void printPrimes(int n)
{
for(int i = 2; i<=n; i++)
{
if(isPrime[i])
System.out.print(i+" ");
}
}```
```// Efficient Code with Sorted Order

static void printDivisors(int n)
{
int i = 1;
// Print all divisors from 1(inlcusive) to sqrt(n) (exclusive)
for(i=1; i*i < n; i++)
{
if(n % i == 0)
{
System.out.print(i+" ");
}
}
// Print all divisors from sqrt(n)(inlcusive) to n (inclusive)
for(; i >= 1; i--)
{
if(n % i == 0)
{
System.out.print((n / i)+" ");
}
}
}

//Efficient Code : Time Complexity: O(sqrt(n)) , Auxiliary Space : O(1)

static void printDivisors(int n)
{
for(int i=1; i*i <= n; i++)
{
if(n % i == 0)
{
System.out.print(i+" ");

if(i != n / i)
System.out.print((n / i)+" ");
}
}
}

// Naive Solution : Time Complexity : O(n) , Auxiliary Space : O(1)

static void printDivisors(int n)
{
for (int i=1;i<=n;i++)
if (n%i==0)
System.out.print(i+" ");
}```
```//Prime Factors in java
//More Efficient Solution : Time Complexity : O(sqrt(n))

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

public class Main {

static void printPrimeFactors(int n)
{
if(n <= 1)
return;

while(n % 2 == 0)
{
System.out.print(2+" ");

n = n / 2;
}

while(n % 3 == 0)
{
System.out.print(3+" ");

n = n / 3;
}

for(int i=5; i*i<=n; i=i+6)
{
while(n % i == 0)
{
System.out.print(i+" ");

n = n / i;
}

while(n % (i + 2) == 0)
{
System.out.print((i + 2)+" ");

n = n / (i + 2);
}
}

if(n > 3)
System.out.print(n+" ");

System.out.println();
}

public static void main (String[] args) {

int n = 450;

printPrimeFactors(n);

}
}

//Efficient Code :

static void printPrimeFactors(int n)
{
if(n <= 1)
return;

for(int i=2; i*i<=n; i++)
{
while(n % i == 0)
{
System.out.print(i+" ");

n = n / i;
}
}

if(n > 1)
System.out.print(n+" ");

System.out.println();
}

// Naive Method : Time Complexity : O(n^2(logn))

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

static void PrimeFactors(int n)
{
for(int i=2; i<n; i++)
{
if(isPrime(i))
{
int x = i;
while(n%x == 0)
{
System.out.print(i+" ");
x = x*i;
}
}
}
}```
```// 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;
}```
```// Efficient Solution : Time Complexity : O(log(min(a,b)))
// a * b = gcd(a,b) * lcm(a,b)

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

public class Main {

static int gcd(int a, int b)
{
if(b==0)
return a;

return gcd(b, a % b);
}

static int lcm(int a, int b)
{
return (a * b) / gcd(a, b); // constant no. of operations
}

public static void main (String[] args) {

int a = 4, b = 6;

System.out.println(lcm(a, b));

}
}

// Naive Method : Time Complexity : O(a*b-max(a,b))

static int lcm(int a, int b)
{
int res = Math.max(a,b);

while(res > 0)
{
if(res%a == 0 && res%b == 0)
{
return res;
}
res++;
}
return res;
}```
```// Optimised Euclidean Algorithm Code : Time Complexity : O(log(min(a,b)))

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

public class Main {

static int gcd(int a, int b)
{
if(b==0)
return a;

return gcd(b, a % b);
}

public static void main (String[] args) {

int a = 12, b = 15;

System.out.println(gcd(a, b));

}
}

// Euclidean Algorithm Code

static int gcd(int a, int b)
{
while(a!=b)
{
if(a > b)
a = a - b;
else
b = b - a;
}

return a;
}

// Naive Method : Time Complexity : O(min(a,b))

static int gcd(int a, int b)
{
int res = Math.min(a,b);

while(res > 0)
{
if(a%res == 0 && b%res == 0)
{
break;
}
res--;
}

return res;
}```
```// Efficient Method : Time Complexity : Θ(logn), Auxiliary Space: O(1)

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

public class Main {

static int countTrailingZeros(int n)
{
int res = 0;

for(int i=5; i<=n; i=i*5)
{
res = res + (n / i);
}

return res;
}

public static void main (String[] args) {

int number = 251;

System.out.println(countTrailingZeros(number));

}
}

// Naive Method : Time Complexity : Θ(n), Auxiliary Space: O(1)

// Overflow for n=20, as factorial value will be of around 19 digits

static int countTrailingZeros(int n)
{
int fact = 1;

for(int i=2; i<=n; i++)
{
fact = fact*i;
}

int res = 0;

while(fact%10 == 0)
{
res++;
fact = fact/10;
}

return res;
}```
star

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

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