Program Prime Factorization in Java

Question

Prime Factorization – Have the user enter a number and find all Prime Factors (if there are any) and display them.

I created one method for verifying if the numbers are prime, and another to check if the input number from user can divide a prime number.

I can't understand why the program is not working and what's the problem with the for loop (Can use functional operations). Please help me!
I'm a beginner and I`d really appreciate if you give me some advice to improve this code.

import java.util.ArrayList;
import java.util.Scanner;


public class PrimeFactors {
    int count, input, num;
    Scanner sc = new Scanner(System.in);
    ArrayList<Integer> factors = new ArrayList();

    public static void main(String[] args) {
        PrimeFactors pfo = new PrimeFactors();
        pfo.primeFactor();


    }

    public void primeFactor(){
        input = sc.nextInt();
        for(num = input; num <= 1; num--){
            System.out.println(input);
            if(isPrime(num)){
                if (divide(num)) {
                    System.out.println("Adding a new int...");
                    factors.add(num);
                    num = input;
                }
            }
        }
        for(int element : factors){
            System.out.println(factors.get(element));
        }
    }

    public boolean isPrime(int number){
        for(int i = 2; i < number; i++){
            if(number % i == 0){
                count++;
            }
        }
        return (count == 0);
    }

    public boolean divide(int number){
        return (input % number == 0);
    } 

}

Answer 1

public class Prime
{
   int i;

   public Prime( )
   {
      i = 2;
   }

   public boolean isPrime( int test ) 
   {
      int k;

      if( test < 2 )
        return false;
    else if( test == 2 )  
        return true;
    else if( ( test > 2 ) && ( test % 2 == 0 ) )
        return false;
    else
    {
        for( k = 3; k < ( test/2 ); k += 2 )
        {
            if( test % k == 0 ) 
                return false;
        }

    }

      return true;

   }

   public void primeFactors( int factorize )
   {
      if( isPrime( factorize ) )
      {
         System.out.println( factorize );
         i = 2;
      }
      else
      {
         if( isPrime( i ) && ( factorize % i == 0 ) )
         {
            System.out.print( i+", " );
            primeFactors( factorize / i );
         }
         else
         {
            i++;
            primeFactors( factorize );
         }
     }

   }   

   public static void main( String[] args )
   {
      Prime p = new Prime( );

      p.primeFactors( 1001 );
      p.primeFactors( 649 );
      p.primeFactors( 144 );

   }

}//end Prime.java

Answer 2

You were using global variables when you should have been using instance variables. A few other typos like what Johnny pointed out. The big thing I changed was that I made this program recursive. Try to stay away from global variables as much as possible, it makes things more confusing (the primeFactor method should be taking in a variable rather than it using a global variable, for instance).

public class PrimeFactors {
    int count;
    static int input;
    int num;
    static Scanner sc = new Scanner(System.in);
    static ArrayList<Integer> factors = new ArrayList();

    public static void main(String[] args) {
        PrimeFactors pfo = new PrimeFactors();
        input = sc.nextInt();
        pfo.primeFactor();
        for(int element : factors){
            System.out.println(element);
        }
    }

    public void primeFactor(){
        if (input > 1) {

            for(int i = input; i >= 1; i--){
                if(isPrime(i)){
                    if (divide(i)) {
                        System.out.println("Adding a new int...");

                        factors.add(i);
                        input = input / i;
                        primeFactor();
                    }
                }
            }

        }
    }

    public boolean isPrime(int number){
        int count = 0;
        for(int i = 2; i < number; i++){
            if(number % i == 0){
                count++;
            }
        }
        return (count == 0);
    }

    public boolean divide(int number){
        return (input % number == 0);
    } 
}

Here's my solution to primeFactors. I left out the calculating the prime list part. Streams are pretty awesome, I've enjoyed trying to use them when solving project Euler problems.

private static ArrayList<Integer> primeFactors(int number) {
        return primeFactors(new ArrayList<Integer>(), number);
    }

    private static ArrayList<Integer> primeFactors(ArrayList<Integer> primeFactors, int number) {
        if (number == 1) {
            return primeFactors;
        }

        int newPrime=primeDividor(number);
        primeFactors.add(newPrime);
        return primeFactors(primeFactors, number/newPrime);
    }

    private static int primeDividor(int input) {
        return primes.stream()
                     .filter(e -> input % e == 0)
                     .findFirst()
                     .orElse(input);
    }

Answer 3

I listened to all your advices and I improved my program using the Sieve of Eratosthenes, i will also be very grateful if you give me some more advices how i can make it better.

    public class PrimeFactors {
    static int input;
    static Scanner sc = new Scanner(System.in);
    static ArrayList<Integer> factors = new ArrayList();

    public static void main(String[] args) {
        PrimeFactors pfo = new PrimeFactors();
        SieveOfEratosthenes sieveObj = new SieveOfEratosthenes();

        input = sc.nextInt();

        sieveObj.findAllPrimeFactors(input);
        pfo.divisiblePrimeFactors(sieveObj.allPrimeFactors);

        for(int element : factors){
            System.out.println(element);
        }
    }

    public void divisiblePrimeFactors(ArrayList<Integer> allPrimeFactors){    
        if(input > 1){

            for(int element : allPrimeFactors){
                if(isDivisible(element, input)){
                    factors.add(element);
                    input = input/element;
                    divisiblePrimeFactors(allPrimeFactors);
                }    
            }
        }    
    }

    public boolean isDivisible(int number, int divisor){
        return (divisor % number == 0);
    } 
}

public class SieveOfEratosthenes {

    ArrayList<Integer> allPrimeFactors= new ArrayList();

    public void findAllPrimeFactors(int limit){
        boolean[] isPrime = new boolean[limit];
        isPrime[0] = false;
        isPrime[1] = false;

        for(int i = 1; i < limit; i++){
            isPrime[i] = true;
        }

        for(int i = 2; i < limit; i++){
            if(isPrime[i]){
                allPrimeFactors.add(i);
            }
            for(int j = i*i; j < limit; j+=i){
                isPrime[j] = false;
            }
        }
    }
}

Answer 4

There are multiple issues with your code. First, your loop in primeFactor will never run for numbers greater that 1. You can fix that by changing your for loop to for(num = 1; num <= input; num++) to test for all the values from 1 to input. But you later overwrite num with input, so it breaks out of the loop automatically.

Second, you never set count at the beginning of the isPrime function to zero, and make it local to the isPrime function (it is not used elsewhere).

Third, you don't need to call factors.get when using a for loop with an iterator, the variable you declared contains the value. So you should remove the call to factors.get(element) and just use element.

These changes gives your code the proper behaviour. There are other ways you can optimize it.

• Name your functions correctly. divide should be called isDivisible and accept two arguments, the number and the divisor.
• Avoid member variables when you can make them local to a function. This gets rid of side-effects. All of the variables in your current class should be locals.

• You should construct a Sieve of Eratosthenes before and then verify if your number is divisible by the numbers in the sieve. It will be much faster than dividing by every number smaller than itself.

  import java.util.ArrayList;
  import java.util.Scanner;
  
  
  public class PrimeFactors {
      int count, input, num;
  Scanner sc = new Scanner(System.in);
  ArrayList<Integer> factors = new ArrayList();
  
  public static void main(String[] args) {
      PrimeFactors pfo = new PrimeFactors();
      pfo.primeFactor();
  }
  
  public void primeFactor(){
      input = sc.nextInt();
      for(num = 1; num <= input; num++){
          if(isPrime(num)){
              if (divide(num)) {
                  System.out.println("Adding a new int...");
                  factors.add(num);
              }
          }
      }
      for(int element : factors){
          System.out.println(element);
      }
  }
  
  public boolean isPrime(int number){
      int count = 0;
  
      for(int i = 2; i < number; i++){
          if(number % i == 0){
              count++;
          }
      }
      return (count == 0);
  }
  
  public boolean divide(int number){
      return (input % number == 0);
  } 
  }