Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Java Program for Finding out the Prime Factors of a Number

Last Updated on May 16, 2023 by Prepbytes

Finding prime factors of a number involves breaking down a given number into its prime factors, which are the prime numbers that divide the original number without leaving a remainder. For example, the prime factors of 12 are 2, 2, and 3, because 2 x 2 x 3 = 12.

There are different approaches to finding the prime factors of a number, but one common method is to use trial division. This method involves dividing the given number by prime numbers starting from 2 until the quotient is no longer divisible by that prime number.

What are Prime Factors?

A factor which is a prime number and not a composite number is a prime factor. For example, 2, 3 and 5 are the prime factors of 30.

Approach to Finding out the Prime Factors of a Number

We have different methods to find out the prime factors of a number.

Method 1: Naive Approach

The algorithm’s stages are as follows:

  • Step 1: Make a function called isprime(int n) that returns 1 if an integer is a prime number and 0 otherwise.
  • Step 2: An iterative loop from 2 to n,
  • Step 3: then determine if it is a prime. n, should be stored in the variable x.
  • Step 4: Run a while loop that ends when (x is not divisible by i) and print i and x = x/2 inside of it.

Code Implementation

import java.io.*;
import java.lang.Math;

class Main {

   public static int isprime(int n){

      for(int i = 2; i<=Math.sqrt(n); i++){
        if(n%i==0)
          return 0;
      }

      return 1;
   }

   public static void primeFactors(int n)
   {

      for(int i = 2; i<= n; i++){
          if(isprime(i)==1){
             int x = n;
             while(x%i==0){
                System.out.print(i + " ");
                x /= i;
             }
          }
       }

   }

   public static void main(String[] args)
   {
       int n = 90;
       primeFactors(n);
   }
}

Output

2 3 3 5

Method 2: Optimised Approach

The algorithm’s stages are as follows:

  • Step 1: Start a while loop that will end whenever the number cannot be divided by two,
  • Step 2: As a result, each time the loop is executed, print("2") and divide the integer by 2 are used.
  • Step 3: N will then be an odd number. Start a loop now, going from i = 3 to the square root of n.
  • Step 4: When i is not divisible by n, run a while loop that ends.
  • Step 5: Print i while in the loop, then divide n by i, increase i by 2, and keep going.
  • Step 6: If n is a prime integer and is larger than 2, the two procedures above will not result in 1 being obtained.
  • Step 7: Therefore, if n is bigger than 2, print n.

Code Implementation

import java.io.*;
import java.lang.Math;

class Main {

  public static void primeFactors(int n)
  {

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

    for (int i = 3; i <= Math.sqrt(n); i += 2) 
    { 
    	while (n % i == 0) 
    	{
    		System.out.print(i + " "); n /= i; 
    		
    	} 
    	
    }
    
    if (n > 2)
    System.out.print(n);
  }

  public static void main(String[] args)
  {
    int n = 90;
    primeFactors(n);
  }
}

Output

2 3 3 5

Conclusion
In conclusion, finding the prime factors of a number involves breaking down the number into its prime factors, which are the prime numbers that can divide the number without leaving a remainder. To do this, you can start by dividing the number by the smallest prime number, which is 2, and then continuing to divide the quotient by the smallest prime number until you reach 1. The prime factors of the original number are the prime numbers that were used in the division process. This method is known as prime factorization and can be done manually or with the help of a computer program.

Frequently Asked Questions

Q1. Why is it important to find the prime factors of a number?
Ans. Prime factorization is an important concept in number theory and has many practical applications in fields such as cryptography, computer science, and finance. For example, in cryptography, the security of many encryption algorithms is based on the difficulty of factoring large numbers into their prime factors.

Q2. How do I find the prime factors of a number?
Ans. To find the prime factors of a number, you can start by dividing the number by the smallest prime number, which is 2. If the number is divisible by 2, divide it by 2 and repeat the process until it is no longer divisible by 2. Then, move on to the next smallest prime number and repeat the process until you have broken down the number into its prime factors.

Q3. What is the prime factorization of a number?
Ans. The prime factorization of a number is a list of its prime factors, along with their multiplicities. For example, the prime factorization of 12 is 2 x 2 x 3, which means that 12 can be expressed as the product of the prime numbers 2 and 3, each raised to a certain power.

Q4. Can every number be factored into primes?
Ans. Yes, every positive integer greater than 1 can be factored into a unique product of primes, known as its prime factorization. This is known as the fundamental theorem of arithmetic.

Leave a Reply

Your email address will not be published. Required fields are marked *