Why does my program for enumerating the prime factors of a list of numbers return unexpected values?

Question

Given a list of integers from a minimum to a maximum, I am trying to find the list of prime factors that evenly multiply into any of the integers in the previously given list.

For example, given as input list of integers [1 ... 10], the program would output [1, 2, 2, 2, 3, 3, 5, 7]. This list contains the prime factors for the list [1 ... 10], because 1*1=1,1*2=2,1*3=3,2*2=4,5*1=5,2*3=6,1*7=7,2*2*2=8,3*3=9, & 2*5=10.

Anyway, in order to do this, I created a method (in Java) to enumerate all the integers from a min to a max. From there, I built a method to find the prime factors of any given integer. Using that prime factors method, I then wrote a method to iterate through a list of integers, keeping a running list of the prime factors needed for these integers without adding any extras that aren't already in this list. For example, if the prime factors for only 2 & 8 are needed, it would find the prime factors of 8 (2, 2, & 2), and the prime factors of 4 (2 & 2). However, because 2 & 2 are already in the list because of 8's prime factors, they won't be added. Of course, there are other helper methods in the program that may very well have bugs, but this is the main structure of it.

I tested this program on the list [1 ... 10] and expected the output [2, 2, 2, 3, 3, 5, 7], but instead got the output [3, 3, 7]. It appears as if, for some reason, when I take the relative complement of the prime factors for a number in the integer list and the running list, some of the numbers in the running list are removed, but I can't figure out why.

Can anyone find this bug and tell me why this is happening?

Code:

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

class Main{

  public static void main(String[] args){

    System.out.println(listPrimeFactors(maxToMin(1, 10)));

  }

  public static ArrayList<Integer> listPrimeFactors(ArrayList<Integer> myList){

    ArrayList<Integer> myFactors = new ArrayList<Integer>();

    for(int j = 0; j < myList.size(); j++){

      myFactors =  addDifference(myFactors, primeFactors(myList.get(j)));

    }
    return myFactors;
  }

  private static ArrayList<Integer> addDifference(ArrayList<Integer> list1, ArrayList<Integer> list2){

    ArrayList<Integer> tempList1 = list1;
    Collections.sort(tempList1);
    Collections.sort(list2);
    for(int i = 0; i < list2.size(); i++){
      if(inList(list2.get(i), tempList1)){
        tempList1.remove(list2.get(i));
        list2.remove(list2.get(i));
      }
    }

    for(int r = 0; r < list2.size(); r++){
      tempList1.add(list2.get(r));
    }
    System.out.println(list2 + " >>> " + tempList1);

    return tempList1;
  }

    private static boolean inList(int n, ArrayList<Integer>  myList){

      for(int k = 0; k < myList.size(); k++){

        if(n == myList.get(k)){ 
          return true;
        } 
      }
      return false;

    }

  public static ArrayList<Integer> primeFactors(int n){ 

    ArrayList<Integer> primeFactorsList = new  ArrayList<Integer>();
    while (n%2==0){ 
      primeFactorsList.add(2); 
      n /= 2; 
    } 
    for (int i = 3; i <= Math.sqrt(n); i+= 2){ 
       while (n%i == 0) { 
         primeFactorsList.add(i); 
         n /= i; 
       } 
   }
    if (n > 2){
      primeFactorsList.add(n);      
    }   
   return primeFactorsList; 
  }

  public static ArrayList<Integer> maxToMin(int min, int max){

    ArrayList<Integer> myList = new ArrayList<Integer>();
    for(int i = max; i >= min; i--){

      myList.add(i);
    }
    return myList;
  }
}

score 1 · Accepted Answer · answered Oct 25 '19 at 08:46

You should not remove items from a list while looping over it without an iterator, see this question. Furthermore you are continuing to work with your temporary list (where elements have been removed already) instead your running list.

Here is an example of those changes:

private static ArrayList<Integer> addDifference(ArrayList<Integer> list1, ArrayList<Integer> list2){
    ArrayList<Integer> tempList1 = new ArrayList<>(list1);
    for (Iterator<Integer> iterator = list2.iterator(); iterator.hasNext();) {
        Integer value = iterator.next();
        if (inList(value, tempList1)) {
            iterator.remove();
            tempList1.remove(value);
        }
    }

    for (int r = 0; r < list2.size(); r++){
        list1.add(list2.get(r));
    }

    System.out.println(list2 + " >>> " + list1);

    return list1;
}

Why does my program for enumerating the prime factors of a list of numbers return unexpected values?

1 Answers1