Java Program for Finding out the Prime Factors of a Number

Last Updated on April 19, 2024 by Abhishek Sharma

In mathematics, the prime factors of a natural number are the prime numbers that divide the number exactly, without leaving a remainder. Finding the prime factors of a number is a common operation in mathematics and programming. In this article, we’ll explore how to write a Java program to find the prime factors of a given number efficiently.

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
Finding the prime factors of a number is a useful mathematical operation that can be implemented efficiently in Java using the above approach. By dividing the number by its prime factors, we can decompose it into its prime factors, which is helpful in various mathematical and algorithmic problems.

Frequently Asked Questions related to Java Program for Finding out the Prime Factors of a Number

Below are some of the FAQs related to Java Program for Finding out the Prime Factors of a Number:

1. How do I find the prime factors of a number in Java?
You can find the prime factors of a number in Java by using the above program, which uses a loop to divide the number by its prime factors starting from 2 up to the square root of the number.

2. Can I find the prime factors of a large number efficiently in Java?
Yes, the above program is efficient for finding the prime factors of large numbers. However, for extremely large numbers, you may need to use more advanced algorithms, such as the Pollard’s rho algorithm or the quadratic sieve algorithm.

3. Is 1 considered a prime factor of a number?
No, 1 is not considered a prime factor of a number because it does not meet the definition of a prime number, which is a number greater than 1 that has no positive divisors other than 1 and itself.

4. Can I optimize the above program further?
Yes, you can optimize the program further by only checking odd numbers as factors (after checking for 2) and by using a more efficient algorithm for checking prime numbers, such as the Sieve of Eratosthenes.

5. How can I handle negative numbers in the program?
The program assumes that the input number is a positive integer. To handle negative numbers, you can add a check to ensure that the input number is positive, or you can modify the program to handle negative numbers separately.