java 中的最大公约数使用质因数分解

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++;
        }
    }
}

对于大块代码很抱歉，但想要 post 目前为止我拥有的所有代码。质因数分解工作正常，现在我想比较两个数组列表并找到共同元素。但是例如 36 和 48 是

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*

如您所见，它不能正常工作，结果应该是 2*2*3，而不是 2*2。如何在整个 arraylist 中找到常见的数字系列，而不是像我的代码现在可以在 arraylist 的开头找到？

Answer 1

您的 while 循环仅查找两个列表的公共前缀。为了找到所有公共元素，您需要使用两个索引遍历两个 Lists :

    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++;
        }
    }

我假设两个 List 中的数字都按升序排序，我认为这是一个正确的假设（如果我正确理解您的代码）。

编辑：

同时更改要参数化的列表的声明：

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

甚至更好：

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

java 中的最大公约数使用质因数分解

Greatest common divisor in java using prime factorizations

java

prime-factoring

greatest-common-divisor