Greatest common divisor in java using prime factorizations

Question

        int a;
        int b;
        int iloscA = 0;
        int iloscB = 0;
        ArrayList liczbyPierwszeA = new ArrayList();
        ArrayList liczbyPierwszeB = new ArrayList();
        Scanner liczba = new Scanner(System.in);
        System.out.println("Podaj a.");
        a = liczba.nextInt();
        System.out.println("Podaj b");
        b = liczba.nextInt();
        int a1 = a;
        int b1 = b;

        for (int i = 2; i <= a; i++) {

            while (a % i == 0) {
                // System.out.print(i + "*");
                liczbyPierwszeA.add(iloscA, i);
                iloscA++;
                a = a / i;
            }
        }

        int x = 0;
        System.out.print("Rozkład na czynniki pierwsze liczby " + a1 + "=");
        while (x < liczbyPierwszeA.size()) {
            System.out.print(liczbyPierwszeA.get(x) + "*");
            x++;
        }

        for (int i = 2; i <= b; i++) {

            while (b % i == 0) {
                // System.out.print(i + "*");
                liczbyPierwszeB.add(iloscB, i);
                iloscB++;
                b = b / i;
            }
        }
        System.out.println("");
        int y = 0;
        System.out.print("Rozkład na czynniki pierwsze liczby " + b1 + "=");
        while (y < liczbyPierwszeB.size()) {
            System.out.print(liczbyPierwszeB.get(y) + "*");
            y++;
        }

        int licznik = 0;
        ArrayList Wspolne = new ArrayList();
        int WspolneLicznik = 0;
        while (liczbyPierwszeA.get(licznik) == liczbyPierwszeB.get(licznik)) {
            Wspolne.add(WspolneLicznik, liczbyPierwszeA.get(licznik));
            licznik++;
            WspolneLicznik++;
        }
        System.out.println("");
        int z = 0;
        while (z < Wspolne.size()) {
            System.out.print(Wspolne.get(z) + "*");
            z++;
        }
    }
}

Soory for the big block of code, but wanted to post all I have so far. Prime factorization works fine, now I wanted to compare both arraylists and find common elements. But for example with 36 and 48 it is

Rozkład na czynniki pierwsze liczby 36=2*2*3*3*
Rozkład na czynniki pierwsze liczby 48=2*2*2*2*3*
2*2*

And it doesn't work right as you can see, result should be 2*2*3, not 2*2. How to find common series of numbers in whole arraylist, not in the beginning of arraylist like my code works right now?

Answer 1

Your while loop only finds the common prefix of the two lists. In order to find all the common elements, you need to iterate over the two Lists using two indices :

    int indexA = 0;
    int indexB = 0;
    while (indexA < liczbyPierwszeA.size () && indexB < liczbyPierwszeB.size()) {
        if (liczbyPierwszeA.get(indexA) == liczbyPierwszeB.get(indexB)) {
            Wspolne.add(WspolneLicznik, liczbyPierwszeA.get(indexA));
            indexA++;
            indexB++;
            WspolneLicznik++; // not sure what this counter is for. I kept it just 
                              // in case it's needed
        } else {
            if (iczbyPierwszeA.get(indexA) < liczbyPierwszeB.get(indexB))
                indexA++;
            else
                indexB++;
        }
    }

I'm assuming the numbers in both Lists are sorted in ascending order, which I think is a correct assumption (if I understood your code correctly).

EDIT :

Also change the declaration of your Lists to be parameterized :

    ArrayList<Integer> liczbyPierwszeA = new ArrayList<Integer>();
    ArrayList<Integer> liczbyPierwszeB = new ArrayList<Integer>();

Or even better :

    List<Integer> liczbyPierwszeA = new ArrayList<Integer>();
    List<Integer> liczbyPierwszeB = new ArrayList<Integer>();