如何排序素数数组

Question

我想按它们的素因式分解对这组数字进行排序。但我目前还不确定如何开始排序。我正在考虑使用散列映射将键和素因式分解存储为数组，并使用比较器对值数组进行排序。以下是我正在努力实现的目标的可视化：

有人能帮忙吗？谢谢!

输入：

3, 4, 8, 9, 12

编辑：这个数字是按照这个顺序排序的，因为数字是按照下面的素因子来区分的(在本例中是2)，然后是3。

Prime Factorization of 4: 2 2 
Prime Factorization of 8: 2 2 2 
Prime Factorization of 12: 2 2 3 
Prime Factorization of 3: 3 
Prime Factorization of 9: 3 3 
and so on...

输出：

4, 8, 12, 3, 9

这里是我的代码：

public class Tester {
    public static void main(String[] args) {
        int[] array = { 3, 4, 8, 9 ,12 };
        for (int i = 0; i < array.length; i++) {
            System.out.print("Prime Factorization of " + array[i] + ": ");
            getPrimeFactors(array[i]);
            System.out.println();
        }
    }

    public static void getPrimeFactors(int number) {
        for (int i = 2; i <= number; i++) {
            while (number % i == 0) {
                System.out.print(i + " ");
                number /= i;
            }
        }
    }
}

Answer 1

要使用自定义比较器，需要将数组转换为Integer[]。

使用自定义比较器对基元数组进行排序，而不转换为对象

你可以很容易地用streams做这件事。

public class Test {
    public static void main(String[] args) {
        int[] array = { 3, 4, 8, 9 ,12 };
        Map<Integer, List<Integer>> factorizations = new HashMap<>();

        for(int num : array) {
            if(factorizations.containsKey(num)) {
                continue;
            }

            factorizations.put(num, factorization(num));
        }

        array = Arrays.stream(array).boxed().sorted((a, b) -> {
            List<Integer> aFactorization = factorizations.get(a);
            List<Integer> bFactorization = factorizations.get(b);

            for(int i = 0; i < Math.min(aFactorization.size(), bFactorization.size()); i++) {
                if(!aFactorization.get(i).equals(bFactorization.get(i))) {
                    return aFactorization.get(i) - bFactorization.get(i);
                }
            }

            if(aFactorization.size() != bFactorization.size()) {
                return aFactorization.size() - bFactorization.size();
            }

            return 0;
        }).mapToInt(Integer::valueOf).toArray();

        System.out.println(Arrays.toString(array));
    }

    public static List<Integer> factorization(int number) {
        List<Integer> factors = new ArrayList<>();

        for (int i = 2; i <= number / i; i++) {
            while (number % i == 0) {
                factors.add(i);
                number /= i;
            }
        }

        if (number > 1) {
            factors.add(number);
        }

        return factors;
    }
}

输出：

[4, 8, 12, 3, 9]

Java流装箱

Answer 2

使用映射存储素因式分解和使用自定义比较器对数组进行排序的想法是可靠的：

Integer[] array = {3, 4, 8, 9, 12};
    
Map<Integer, Integer[]> map = new HashMap<>();
for(int a : array) map.putIfAbsent(a, getPrimeFactors(a));
    
Arrays.sort(array, (a, b) -> Arrays.compare(map.get(a), map.get(b)));
    
System.out.println(Arrays.toString(array));

输出：

[4, 8, 12, 3, 9]

我们拥有的地方：

public static Integer[] getPrimeFactors(int n)
{
    List<Integer> pfs = new ArrayList<>();

    for (; n % 2 == 0; n /= 2) pfs.add(2);

    for (int i = 3; i * i <= n; i += 2)
        for (; n % i == 0; n /= i) pfs.add(i);

    if (n > 1) pfs.add(n);

    return pfs.toArray(new Integer[0]);
}

Answer 3

首先重写getPrimeFactors方法以返回主要因素列表：

public static List<Integer> getPrimeFactors(int number) {
        List<Integer> primeFactors = new ArrayList<Integer>();
        for (int i = 2; i <= number; i++) {
            while (number % i == 0) {
                primeFactors.add(i);
                number /= i;
            }
        }
        return primeFactors;
    }

现在，您的高级目标是按字典顺序对素因式分解进行排序。为此，我们将每个素因子列表转换为一个String，将每个素因子映射为一个字符。然后根据素因子列表的String版本进行排序。最后，我们输出列表。下面是重写的main方法，它就是这样做的：

public static void main(String[] args) {
        int[] array = { 3, 4, 8, 9, 12 };
        String[][] numsAndFactors = new String[array.length][];
        for (int i = 0; i < array.length; i++) {
            String primeFactorsToChars = "";
            List<Integer> primeFactors = getPrimeFactors(array[i]);
            for (int primeNumber : primeFactors) {
                primeFactorsToChars += (char) (primeNumber + 48);
            }
            numsAndFactors[i] = new String[] {Integer.toString(array[i]), primeFactorsToChars};

        }
        Arrays.sort(numsAndFactors, (a, b) -> a[1].compareTo(b[1]));

        for (String[] numberAndFactors : numsAndFactors) {
            System.out.print("Prime factorization of " + numberAndFactors[0] + ": ");
            String factors = numberAndFactors[1];
            for (char c : factors.toCharArray()) {
                System.out.print((int) (c - 48) + ", ");
            }
            System.out.println("");
        }
    }

输出：

Prime factorization of 4: 2, 2, 
Prime factorization of 8: 2, 2, 2,
Prime factorization of 12: 2, 2, 3,
Prime factorization of 3: 3,
Prime factorization of 9: 3, 3,