Prime Factors

PHOTO EMBED

Sun Feb 06 2022 04:39:27 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #mathematics #lecture #gfg #geeksforgeeks #efficientmethod #naivemethod #primefactors 

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

Prime factor is the factor of the given number which is a prime number. Factors are the numbers you multiply together to get another number. In simple words, prime factor is finding which prime numbers multiply together to make the original number. Example: The prime factors of 15 are 3 and 5 (because 3×5=15, and 3 and 5 are prime numbers). Naive solution: ----------------- Given a number n, write a function to print all prime factors of n. For example, if the input number is 12, then output should be “2 2 3” and if the input number is 315, then output should be “3 3 5 7”. Following are the steps to find all prime factors: While n is divisible by 2, print 2 and divide n by 2. After step 1, n must be odd. Now start a loop from i = 3 to square root of n. While i divides n, print i and divide n by i, increment i by 2 and continue. If n is a prime number and is greater than 2, then n will not become 1 by above two steps. So print n if it is greater than 2. Efficient Solution: ------------------- 1.) Divisors always appear in pairs 30 : (1,30) , (2,15) , (3,10) , (5,6) 2.) A number n can be written as multiplications of powers of prime factors 12 = 2^2 * 3 450 = 2^1 * 3^2 * 5^2 ________________________ Let (x,y) be a pair x * y = n If x<=y x * x <= n x <= sqrt(n)