如何排序素数数组

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 stream boxed

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,

Answer 4

要在没有比较器的情况下执行相同的操作，可以使用简单的选择排序(效率不高)，如下所示。这并不需要使用集合。

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


public static void main(String[] args) {
int arr[] = {3,4,8,9,12};
String factorArr[] = new String[arr.length];
for(int i = 0; i<arr.length; i++) {
factorArr[i] = getPrimeFactors(arr[i]);
}

for(int i = 0; i<arr.length - 1; i++) {
int min = i;
for(int j = i+1; j<arr.length; j++) {
if(factorArr[j].compareTo(factorArr[min]) < 0) {
min = j;
}
}
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;

String temp2 = factorArr[min];
factorArr[min] = factorArr[i];
factorArr[i] = temp2;
}

for(int i = 0; i<arr.length; i++) {
System.out.println("Number: " + arr[i] + " & Factors: " + factorArr[i]);
}
}
}

这里，我只是将质因数分解存储为一个字符串数组，其索引与原始数组中的索引相对应。然后，我们对分解字符串进行排序，并在进行交换时对原始数字数组进行更改，以保持索引彼此对应。

结果，我们有两个数组，一个数组的初始数字按您想要的顺序排序，另一个数组是它们的质数因子对应项。虽然这不是最有效的方法，但它应该相当容易理解，并在以后需要时进行更改。